Small Convex Quadrangulations of Point Sets

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⌊n∣2⌋ internal Steiner points are always sufficient for a convex quadrangulation of n points in the plane. Furthermore, for any given n ≥ 4, there are point sets for which $$ \left[ {\tfrac{{n - 3}}