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\lfloorn/2\rfloor internal Steiner points are always sufficient for a convex quadrilateral mesh of n points in the plane. Furthermore, for any given n\geq 4, there are point sets for which \lceil(n–3)/2\rceil–1 Steiner points are necessary for a convex quadrilateral mesh.