Small Strictly Convex Quadrilateral Meshes of Point Sets

Abstract

In this paper, we give upper and lower bounds on the number of Steiner points required to construct a strictly convex quadrilateral mesh for a planar point set. In particular, we show that $3\lfloor \frac{n}{2}\rfloor$ internal Steiner points are always sufficient for a convex quadrilateral mesh of $n$ points in the plane. Furthermore, for any given $n\ge 4$, there are point sets for which $\lceil \frac{n-3}{2}\rceil -1$ Steiner points are necessary for a convex quadrilateral mesh.

25 pages, 23 figures. A preliminary version appeared in ISAAC 2001, Christchurch NZ