Peyman Afshani, Boris Aronov, Kevin Buchin, Maike Buchin, Otfried Cheong, Katharina Klost, Carolin Rehs, and Günter Rote:

Compatible triangulations of simple polygons

Abstract

Let P and Q be simple polygons with n vertices each. We wish to compute triangulations of P and Q that are combinatorially equivalent, if they exist. We consider two versions of the problem: if a triangulation of P is given, we can decide in O(n log n+nr) time if Q has a compatible triangulation, where r is the number of reflex vertices of Q. If we are already given the correspondence between vertices of P and Q (but no triangulation), we can find compatible triangulations of P and Q in time O(M(n)), where M(n) is the running time for multiplying two n×n matrices.