Small convex quadrangulations of point sets

David Bremner, Ferran Hurtado, Suneeta Ramaswami, Vera Sacristán

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Scopus citations


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.

Original languageEnglish (US)
Title of host publicationAlgorithms and Computation - 12th International Symposium, ISAAC 2001, Proceedings
Number of pages13
StatePublished - 2001
Event12th International Symposium on Algorithms and Computation, ISAAC 2001 - Christchurch, New Zealand
Duration: Dec 19 2001Dec 21 2001

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2223 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other12th International Symposium on Algorithms and Computation, ISAAC 2001
Country/TerritoryNew Zealand

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Small convex quadrangulations of point sets'. Together they form a unique fingerprint.

Cite this