next up previous
Next: Problem 26: Surface Reconstruction Up: The Open Problems Project Previous: Problem 24: Polygonal Curve


Problem 25: Polyhedral Surface Approximation

Statement
How efficiently can one compute a polyhedral surface that is an ε-approximation of a given triangulated surface in $ \mathbb {R}$3?
Origin
Mitchell [?]
Status/Conjectures
Open.
Partial and Related Results
It is NP-hard to obtain the minimum-facet surface separating two nested convex polytopes [DG97], but polynomial-time approximation algorithms are known ([BG95,MS95,AS98]) for this case, and for separating two terrain surfaces, achieving factors within O(1) or O(log n) of optimal. However, no polynomial-time approximation results are known for general surfaces.
Appearances
[MO01]
Categories
simplification
Entry Revision History
J. O'Rourke, 2 Aug. 2001.

Bibliography

AS98
P. K. Agarwal and S. Suri.
Surface approximation and geometric partitions.
SIAM J. Comput., 27:1016-1035, 1998.

BG95
H. Brönnimann and M. T. Goodrich.
Almost optimal set covers in finite VC-dimension.
Discrete Comput. Geom., 14:263-279, 1995.

DG97
G. Das and M. T. Goodrich.
On the complexity of optimization problems for 3-dimensional convex polyhedra and decision trees.
Comput. Geom. Theory Appl., 8:123-137, 1997.

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.

MS95
Joseph S. B. Mitchell and Subhash Suri.
Separation and approximation of polyhedral objects.
Comput. Geom. Theory Appl., 5:95-114, 1995.



The Open Problems Project - December 04, 2015