Constructing Piecewise Linear Homeomorphisms of Simple Polygons

Let P and Q be simple polygons with vertex sets {p_l,..., p_n] and {q_l,..., q_n], respectively. We present an algorithm to construct a piecewise linear homeomorphism between P and Q mapping each vertex p_i ∈ P to q_i ∈ Q by constructing isomorphic triangulations of P and Q. These isomorphic triangulations consist of O(M log n + n log² n) triangles where M is the size of the optimal (minimum size) solution. The algorithm runs in O(M log n + n log² n) time. We also give an O(n + L + k log k) algorithm for constructing k pairwise disjoint interior paths between k pairs of vertices in a simple polygon on n vertices using O(L + k log k) links. The number L is the sum of the interior link distances between the k pairs of vertices.