TY - JOUR

T1 - Converting triangulations to quadrangulations

AU - Ramaswamia, Suneeta

AU - Ramos, Pedro

AU - Toussaint, Godfried

N1 - Funding Information:
~ The first and third authors were supported by NSERC Grant No. OGP0009293 and FCAR Grant No. 93-ER-0291. The second author's research was carried out during his visit to McGill University in 1995 and was self-supported. * Corresponding author. E-mail: ramaswam@cs.mcgill.ca; rsuneeta@crab.rutgers.edu.

PY - 1998/3

Y1 - 1998/3

N2 - We study the problem of converting triangulated domains to quadrangulations, under a variety of constraints. We obtain a variety of characterizations for when a triangulation (of some structure such as a polygon, set of points, line segments or planar subdivision) admits a quadrangulation without the use of Steiner points, or with a bounded number of Steiner points. We also investigate the effect of demanding that the Steiner points be added in the interior or exterior of a triangulated simple polygon and propose efficient algorithms for accomplishing these tasks. For example, we give a linear-time method that quadrangulates a triangulated simple polygon with the minimum number of outer Steiner points required for that triangulation. We show that this minimum can be at most [n/3], and that there exist polygons that require this many such Steiner points. We also show that a triangulated simple n-gon may be quadrangulated with at most [n/4] Steiner points inside the polygon and at most one outside. This algorithm also allows us to obtain, in linear time, quadrangulations from general triangulated domains (such as triangulations of polygons with holes, a set of points or line segments) with a bounded number of Steiner points.

AB - We study the problem of converting triangulated domains to quadrangulations, under a variety of constraints. We obtain a variety of characterizations for when a triangulation (of some structure such as a polygon, set of points, line segments or planar subdivision) admits a quadrangulation without the use of Steiner points, or with a bounded number of Steiner points. We also investigate the effect of demanding that the Steiner points be added in the interior or exterior of a triangulated simple polygon and propose efficient algorithms for accomplishing these tasks. For example, we give a linear-time method that quadrangulates a triangulated simple polygon with the minimum number of outer Steiner points required for that triangulation. We show that this minimum can be at most [n/3], and that there exist polygons that require this many such Steiner points. We also show that a triangulated simple n-gon may be quadrangulated with at most [n/4] Steiner points inside the polygon and at most one outside. This algorithm also allows us to obtain, in linear time, quadrangulations from general triangulated domains (such as triangulations of polygons with holes, a set of points or line segments) with a bounded number of Steiner points.

KW - Finite element methods

KW - Matchings

KW - Mesh-generation

KW - Quadrangulations

KW - Scattered data interpolation

KW - Simple polygons

KW - Triangulations

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

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

U2 - 10.1016/s0925-7721(97)00019-9

DO - 10.1016/s0925-7721(97)00019-9

M3 - Article

AN - SCOPUS:0009943654

SN - 0925-7721

VL - 9

SP - 257

EP - 276

JO - Computational Geometry: Theory and Applications

JF - Computational Geometry: Theory and Applications

IS - 4

ER -