Polyhedral Surface Approximation

How efficiently can one compute a polyhedral surface that is an $\epsilon$ -approximation of a given triangulated surface in $\mathbb{R}^3$ ?

Download

Abstract

Given a triangulated surface in three dimensions and a tolerance, efficiently construct a simpler polyhedral surface within the prescribed error.

Background and progress

Minimum-facet separation is NP-hard even for nested convex polytopes [Das and Goodrich, 1997]. Approximation results are known for restricted settings such as terrains [Agarwal and Suri, 1998], but no general polynomial-time approximation guarantee is reported. The original problem appears in the Open Problems Project at https://topp.openproblem.net/p25.

Reference papers

On the complexity of optimization problems for 3-dimensional convex polyhedra and decision treesGautam Das, Michael T. GoodrichProceedings of the 13th Annual Symposium on Computational Geometry · 1997
Surface approximation and geometric partitionsPankaj K. Agarwal, Subhash SuriSIAM Journal on Computing · 1998

Polyhedral Surface Approximation

Coming soon

Organizer