Small Strictly Convex Quadrilateral Meshes of Point Sets
<|reference_start|>Small Strictly Convex Quadrilateral Meshes 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{\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.<|reference_end|>
@article{bremner2002small,
    title={Small Strictly Convex Quadrilateral Meshes of Point Sets},
    author={David Bremner, Ferran Hurtado, Suneeta Ramaswami, and Vera Sacristan},
    journal={arXiv preprint arXiv:cs/0202011},
    year={2002},
    archivePrefix={arXiv},
    eprint={cs/0202011},
    primaryClass={cs.CG}
}