TY - JOUR
T1 - On compatible triangulations of simple polygons
AU - Aronov, Boris
AU - Seidel, Raimund
AU - Souvaine, Diane
N1 - Funding Information:
Brooklyn, NY 11201, USA. * Work on this paper was supported by DIMACS( Center for Discrete Mathematics and Theoretical Computer Science), a National Science Foundation Science and Technology Center-NSF-STC88-09648, National Science Foundation Grant CCR-8803549, and NSF Presidential Young Investigator Award CCR-9058440.
PY - 1993/6
Y1 - 1993/6
N2 - It is well known that, given two simple n-sided polygons, it may not be possible to triangulate the two polygons in a compatible fashion, if one's choice of triangulation vertices is restricted to polygon corners. Is it always possible to produce compatible triangulations if additional vertices inside the polygon are allowed? We give a positive answer and construct a pair of such triangulations with O(n2) new triangulation vertices. Moreover, we show that there exists a 'universal' way of triangulating an n-sided polygon with O(n2) extra triangulation vertices. Finally, we also show that creating compatible triangulations requires a quadratic number of extra vertices in the worst case.
AB - It is well known that, given two simple n-sided polygons, it may not be possible to triangulate the two polygons in a compatible fashion, if one's choice of triangulation vertices is restricted to polygon corners. Is it always possible to produce compatible triangulations if additional vertices inside the polygon are allowed? We give a positive answer and construct a pair of such triangulations with O(n2) new triangulation vertices. Moreover, we show that there exists a 'universal' way of triangulating an n-sided polygon with O(n2) extra triangulation vertices. Finally, we also show that creating compatible triangulations requires a quadratic number of extra vertices in the worst case.
UR - http://www.scopus.com/inward/record.url?scp=0002312196&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0002312196&partnerID=8YFLogxK
U2 - 10.1016/0925-7721(93)90028-5
DO - 10.1016/0925-7721(93)90028-5
M3 - Article
AN - SCOPUS:0002312196
SN - 0925-7721
VL - 3
SP - 27
EP - 35
JO - Computational Geometry: Theory and Applications
JF - Computational Geometry: Theory and Applications
IS - 1
ER -