Constrained quadrilateral meshes of bounded size

Suneeta Ramaswami, Marcelo Siqueira, Tessa Sundaram, Jean Gallier, James Gee

Research output: Contribution to journalArticlepeer-review

6 Scopus citations


We introduce a new algorithm to convert triangular meshes of polygonal regions, with or without holes, into strictly convex quadrilateral meshes of small bounded size. Our algorithm includes all vertices of the triangular mesh in the quadrilateral mesh, but may add extra vertices (called Steiner points). We show that if the input triangular mesh has t triangles, our algorithm produces a mesh with at most [3t/2] + 2 quadrilaterals by adding at most t + 2 Steiner points, one of which may be placed outside the triangular mesh domain. We also describe an extension of our algorithm to convert constrained triangular meshes into constrained quadrilateral ones. We show that if the input constrained triangular mesh has t triangles and its dual graph has h connected components, the resulting constrained quadrilateral mesh has at most [3t/2] + 4h quadrilaterals and at most t + 3h Steiner points, one of which may be placed outside the triangular mesh domain. Examples of meshes generated by our algorithm, and an evaluation of the quality of these meshes with respect to a quadrilateral shape quality criterion are presented as well.

Original languageAmerican English
Pages (from-to)55-98
Number of pages44
JournalInternational Journal of Computational Geometry and Applications
Issue number1
StatePublished - 2005

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Computational Theory and Mathematics
  • Computational Mathematics
  • Applied Mathematics


  • Quadrilateral mesh
  • The finite-element method
  • Triangulation


Dive into the research topics of 'Constrained quadrilateral meshes of bounded size'. Together they form a unique fingerprint.

Cite this