Constrained quadrilateral meshes of bounded size

TY - JOUR

T1 - Constrained quadrilateral meshes of bounded size

AU - Ramaswami, Suneeta

AU - Siqueira, Marcelo

AU - Sundaram, Tessa

AU - Gallier, Jean

AU - Gee, James

N1 - Funding Information: *The first and second author's research were partially supported by NSF Grant No. CCR-0204293.

PY - 2005

Y1 - 2005

N2 - 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.

AB - 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.

KW - Quadrilateral mesh

KW - The finite-element method

KW - Triangulation

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

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

U2 - https://doi.org/10.1142/S0218195905001609

DO - https://doi.org/10.1142/S0218195905001609

M3 - Article

SN - 0218-1959

VL - 15

SP - 55

EP - 98

JO - International Journal of Computational Geometry and Applications

JF - International Journal of Computational Geometry and Applications

IS - 1

ER -