Title
Minimum Strictly Convex Quadrangulations of Convex
Polygons
Authors
-
Publication
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
Source
-
Classification
-
not available
Keywords
-
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.
