ON COMPATIBLE TRIANGULATIONS OF SIMPLE POLYGONS

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(n = 2) new triangulation vertices. Moreover, we show that there exists a 'universal' way of triangulating an n-sided polygon with O(n = 2) extra triangulation vertices. Finally, we also show that creating compatible triangulations requires a quadratic number of extra vertices in the worst case.