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.