The Open Problems Project

Next: Problem 27: Hexahedral Meshing

Previous: Problem 25: Polyhedral Surface Approximation

Problem 26: Surface Reconstruction

Statement

Given a sufficiently dense sample of points on a surface (technically, an \epsilon-sample), reconstruct a surface homeomorphic to the original.

Origin

Amenta and Bern [?]

Status/Conjectures

Open.

Partial and Related Results

This has recently been accomplished for smooth surfaces [ACDL00], but remains open for surfaces with sharp edges and corners.

Appearances

[MO01]

Categories

reconstruction; point sets

Entry Revision History

J. O’Rourke, 2 Aug. 2001.

Bibliography

[ACDL00]

N. Amenta, S. Choi, T. K. Dey, and N. Leekha. A simple algorithm for homeomorphic surface reconstruction. In Proc. 16th Annu. ACM Sympos. Comput. Geom., pages 213–222, 2000.

[MO01]

J. S. B. Mitchell and Joseph O’Rourke. Computational geometry column 42. Internat. J. Comput. Geom. Appl., 11(5):573–582, 2001. Also in SIGACT News 32(3):63-72 (2001), Issue 120.