Minimum Strictly Convex Quadrangulations of Convex Polygons

Matthias Müller-Hannemann and Karsten Weihe

an extended abstract appeared in the Proceedings of the 13th Annual ACM Symposium on Computational Geometry, SoCG'97, June 4-6, 1997, Nice, France, pages 193-202

not available

not available

We present a linear-time algorithm that decomposes a convex polygon conformally into a minimum number of strictly convex quadrilaterals. Moreover, we characterize the polygons that can be decomposed without additional vertices inside the polygon, and we present a linear-time algorithm for such decompositions, too. As an application, we consider the problem of constructing a minimum conformal refinement of a mesh in the three-dimensional space, which approximates the surface of a workpiece. The latter problem has resulted from a cooperation with an engineering company that sells CAD packages. We have proved that this problem is strongly NP-hard, and we present a linear-time algorithm with a constant approximation ratio of 4.

Download as [ps.Z]