Small Strictly Convex Quadrilateral Meshes of Point Sets
Loading...
Date
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Description
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\geq 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
25 pages, 23 figures. A preliminary version appeared in ISAAC 2001, Christchurch NZ