On compatible triangulations of simple polygons

Boris Aronov, Raimund Seidel, Diane Souvaine

    Research output: Contribution to journalArticlepeer-review


    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.

    Original languageEnglish (US)
    Pages (from-to)27-35
    Number of pages9
    JournalComputational Geometry: Theory and Applications
    Issue number1
    StatePublished - Jun 1993

    ASJC Scopus subject areas

    • Computer Science Applications
    • Geometry and Topology
    • Control and Optimization
    • Computational Theory and Mathematics
    • Computational Mathematics


    Dive into the research topics of 'On compatible triangulations of simple polygons'. Together they form a unique fingerprint.

    Cite this