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

Abstract

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 languageEnglish (US)
Pages (from-to)55-98
Number of pages44
JournalInternational Journal of Computational Geometry and Applications
Volume15
Issue number1
DOIs
StatePublished - 2005

All Science Journal Classification (ASJC) codes

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

Keywords

  • Quadrilateral mesh
  • The finite-element method
  • Triangulation

Fingerprint

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

Cite this