On Quadrilaterizations of Point Sets on the Plane

Jorge Urrutia
Instituto de Matemáticas,
Universidad Nacionál Autónoma de México,
México

Abstract

Let P be a set of n points on the plane in general position, n 4. A quadrilaterization Q of P is a partitioning of the convex hull of P into a set of quadrilaterals, not necessarily convex, such that the vertices of the quadrilaterals of Q are elements of P, and no element of P lies in the interior of any quadrilateral. It is straightforward to see that if P admits a quadrilaterization, its convex hull must have an even number of vertices.
If the quadrilaterals of Q are convex, we call Q a convex quadrilaterization of P. We say that P is bicolored if P=RB. We call the elements of R the red points of P, and the elements of B the blue points of P. A quadrilaterization Q of a bicolored point set P, is a quadrilaterization of P in which all the edges of the quadrilaterals of Q join a blue to a red point.
It is easy to see that not all point sets admit a convex quadrilaterization, and that with the addition of extra points, Steiner points, we can always obtain point sets that have quadrilaterizations. In this talk we will study the following type of questions: How many Steiner points are necessary to add to any point set so that the resulting point set admits a quadrilaterization (convex quadrilaterization). We also study the bichromatic case. As a biproduct we obtain some tight results on quedrilaterizations of polygons, and partitionings into star-shaped polygons of the convex hull of point sets.