Quadrangulations of Planar Sets

Given a set S such as a polygon or a set of points, a quadrangulation of S is a partition of the interior of S, if S is a polygon, or the interior of the convex hull of S, if S is a set of points, into quadrangles (quadrilaterals) obtained by inserting edges between pairs of points (diagonals between vertices of the polygon) such that the edges intersect each other only at their end points. Not all polygons or sets of points admit quadrangulations, even when the quadrangles are not required to be convex (convex quadrangulations) . In this paper we briefly survey some recent results concerning the characterization of those planar sets that always admit quadrangulations (convex and non-convex) as well as some related computational problems. 1. Introduction In the field of computational geometry a triangulation of a finite planar set such as a set of points, line segments or polygon, is a well studied structure [O'R94], [PS85]. For one thing, a triangulation always exists and for anothe..