On Convex Quadrangulations of Point Sets on the Plane.

Let Pn be a set of n points on the plane in general position, n ≥ 4. A convex quadrangulation of Pn is a partitioning of the convex hull $\mathit{Conv}(P_n)$ of Pn into a set of quadrilaterals such that their vertices are elements of Pn, and no element of Pn 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 Pn has an even number of points, then by adding at most $\frac{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 $\frac{n}{4}$ Steiner points are sometimes necessary. In this paper we show how to improve the upper and lower bounds of [6] to $\frac{4n}{5}+2$ and to $\frac{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 $\frac{4n}{5}+2$, for details see [9]. [ABSTRACT FROM AUTHOR]