On convex quadrangulations of point sets on the plane

Abstract

Let P-n be a set of n points on the plane in general position, n >= 4. A convex quadrangulation of P-n is a partitioning of the convex hull Conv(P-n) of P-n into a set of quadrilaterals such that their vertices are elements of P-n, and no element of P-n 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. In [6] it was proved that if the convex hull of P-n has an even number of points, then by adding at most 3n/2 Steiner points in the interior of its convex hull, we can always obtain a point set that admits a convex quadrangulation. The authors also show that n/4 Steiner points are sometimes necessary. In this paper we show how to improve the upper and lower bounds of [6] to 4n/5 + 2 and to n/3 respectively. In fact, in this paper we prove an upper bound of n, and with a long and unenlightening case analysis (over fifty cases!) we can improve the upper bound to 4n/5 + 2, for details see [9].