The Open Problems Project

Next: Problem 26: Surface Reconstruction

Previous: Problem 24: Polygonal Curve Simplification

Problem 25: Polyhedral Surface Approximation

Statement

How efficiently can one compute a polyhedral surface that is an \epsilon-approximation of a given triangulated surface in \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], if they are allowed to have distinct structures; the complexity is open when one polytope is an offset of the other (e.g., if they arise as offsets of an underlying convex polytope that we seek to approximate). Polynomial-time approximation algorithms are known ([BG95], [MS95], [AS98]) for the case of nested convex polyhedra, 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; J. Mitchell, 14 Oct 2020.

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.