Small Strictly Convex Quadrilateral Meshes of Point Sets

Simple item page
dc.creatorBremner, David
dc.creatorHurtado, Ferran
dc.creatorRamaswami, Suneeta
dc.creatorSacristan, Vera
dc.date2002-02-12
dc.date.accessioned2026-07-07T03:18:07Z
dc.date.available2026-07-07T03:18:07Z
dc.descriptionIn 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.
dc.description25 pages, 23 figures. A preliminary version appeared in ISAAC 2001, Christchurch NZ
dc.identifierhttps://arxiv.org/abs/cs/0202011
dc.identifierhttp://arxiv.org/abs/cs/0202011
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/30984
dc.subjectComputational Geometry
dc.subjectF.2.2
dc.titleSmall Strictly Convex Quadrilateral Meshes of Point Sets
dc.typetext

Files

Collections

arXiv