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 -