Small Strictly Convex Quadrilateral Meshes of Point Sets

الأصل · EN

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/2 internal Steiner points are always sufficient for a convex quadrilateral mesh of n points in the plane. Furthermore, for any given n≥ 4, there are point sets for which -3/2-1 Steiner points are necessary for a convex quadrilateral mesh.