direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Logo der TU Berlin

Inhalt des Dokuments

Preprint 519-1996

Combinatorial Optimization & Graph Algorithms group (COGA-Preprints)

Minimum Strictly Convex Quadrangulations of Convex Polygons
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]
Title: Source

Zusatzinformationen / Extras


Schnellnavigation zur Seite über Nummerneingabe