TY - GEN

T1 - Small convex quadrangulations of point sets

AU - Bremner, David

AU - Hurtado, Ferran

AU - Ramaswami, Suneeta

AU - Sacristán, Vera

PY - 2001

Y1 - 2001

N2 - 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 ⌋n-3/2⌋-1 Steiner points are necessary for a convex quadrangulation.

AB - 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 ⌋n-3/2⌋-1 Steiner points are necessary for a convex quadrangulation.

UR - http://www.scopus.com/inward/record.url?scp=71049138222&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=71049138222&partnerID=8YFLogxK

U2 - 10.1007/3-540-45678-3_53

DO - 10.1007/3-540-45678-3_53

M3 - Conference contribution

AN - SCOPUS:71049138222

SN - 3540429859

SN - 9783540429852

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 623

EP - 635

BT - Algorithms and Computation - 12th International Symposium, ISAAC 2001, Proceedings

T2 - 12th International Symposium on Algorithms and Computation, ISAAC 2001

Y2 - 19 December 2001 through 21 December 2001

ER -