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: [email protected]; [email protected].
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 -