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
^{3}?
 Origin
 Mitchell [?]
 Status/Conjectures
 Open.
 Partial and Related Results
 It is NPhard to obtain the minimumfacet surface
separating two nested convex polytopes [DG97],
but
polynomialtime 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 polynomialtime approximation results
are known for general surfaces.
 Appearances
 [MO01]
 Categories
 simplification
 Entry Revision History
 J. O'Rourke, 2 Aug. 2001.
 AS98

P. K. Agarwal and S. Suri.
Surface approximation and geometric partitions.
SIAM J. Comput., 27:10161035, 1998.
 BG95

H. Brönnimann and M. T. Goodrich.
Almost optimal set covers in finite VCdimension.
Discrete Comput. Geom., 14:263279, 1995.
 DG97

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

J. S. B. Mitchell and Joseph O'Rourke.
Computational geometry column 42.
Internat. J. Comput. Geom. Appl., 11(5):573582, 2001.
Also in SIGACT News 32(3):6372 (2001), Issue 120.
 MS95

Joseph S. B. Mitchell and Subhash Suri.
Separation and approximation of polyhedral objects.
Comput. Geom. Theory Appl., 5:95114, 1995.
The Open Problems Project  September 19, 2017