CONSTRUCTING PIECEWISE-LINEAR HOMEOMORPHISMS OF SIMPLE POLYGONS

Let P and Q be simple polygons with vertex sets {p(1),...,p(n)} and {q (1),...,q(n)}, respectively. We present an algorithm to construct a pi ecewise linear homeomorphism between P and Q mapping each vertex p(i) is an element of P to q(i) is an element of Q by constructing isomorph ic triangulations of P and Q. These isomorphic triangulations consist of O(M log n + n log(2) n) triangles where M is the size of the optima l (minimum size) solution. The algorithm runs in O(M log n + n log(2) 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 s imple polygon on n vertices using O(L + k log k) links. The number L i s the sum of the interior link distances between the k pairs of vertic es. (C) 1997 Academic Press.