Det är väl känt att, med tanke på två enkla n-sidiga polygoner, det kanske inte är möjligt att triangulera de två polygonerna på ett kompatibelt sätt, om ens val av triangulation hörn är begränsad till polygon hörn. Är det alltid möjligt att producera kompatibla trianguleringar om ytterligare hörn inuti polygonen är tillåtna? Vi ger ett positivt svar och konstruerar ett par sådana trianguleringar med O(n 2 ) nya triangulation hörn. Dessutom visar vi att det finns ett \universal" sätt att triangulera en n-sidig polygon med O(n 2 ) extra triangulation hörn. Slutligen visar vi också att skapandet av kompatibla trianguleringar kräver ett kvadratiskt antal extra hörn i värsta fall. Eftersom två enkla polygoner P 1 och P 2, var och en med n hörn, är det inte alltid möjligt att nd kompatibla trianguleringar av de två polygoner. Med andra ord, det kan inte finnas en cirkulär märkning av hörnen av varje polygon genom på varandra följande nummer 1 till n och en uppsättning n? 3 icke-korsande inre ackord i P 1, så att de öppna ackord som förenar motsvarande hörn i P 2 är åtskilda och ligger helt inuti P 2. Överväg gure 1 till här varje hexagon medger en unik triangulering, men de två trianguleringar är inte kompatibla i ovanstående mening, eftersom de tre inre ackord \fan ut" från en gemensam vertex i P 1 och bildar en triangel i P 2. Följande fråga ställdes av Goodman och Pollack G: Är det möjligt att triangulera två polygoner med samma antal hörn kompatibelt om ytterligare hörn (Steiner punkter) är tillåtna i det inre? Om ja, hur många sådana punkter krävs?
REF visar att två enkla polygoner kan trianguleras på ett kompatibelt sätt genom att använda högst O(n 2 ) Steiner hörn, där n är antalet punkter i varje polygon.
On Compatible Triangulations of Simple Polygons
{'venue': 'Comput. Geom.', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}