Minimum strictly convex quadrangulations of convex polygons
Matthias Müller‐Hannemann, Karsten Weihe · 1997
We presenta linear-time afgorithmthatdecomposesa convex polygon conformablyinto a minimum numberof strictly convex quadrilaterals.Morezwer, wecharacterize thepolygons that cm be decomposed without additional vertices inside the polygon, and we presentalinear-time algorithtnforsuch decompositions, too.As an application, we consider theproblem of constructinga minimum conformal refinement of a mesh in the three-dimensional space, which approximates the surface of a workpiece.It turns out that this problem is AfP-hard, and we presenta linear-timealgorithm with a constantapproximationratio of 4. Conformal decompositionsof polygons. Conformalquadrangu-Iationsof polygons is a fundamentalproblem and has applications in finiteelement methods, watchguardproblems, and scattereddata interpolation.See [Tou95] for a survey of this topic and its applications.