On Convex Quadrangulations of Point Sets on the Plane

摘要

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 quadrilateri- zation, its convex hull must have an even number of vertices. In 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 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].