Constructing Piecewise Linear Homeomorphisms of Simple Polygons
Himanshu Gupta, Rephael Wenger · Journal of Algorithms · 1997
LetPandQbe simple polygons with vertex sets {p1,…,pn} and {q1,…,qn}, respectively. We present an algorithm to construct a piecewise linear homeomorphism betweenPandQmapping each vertexpi∈Ptoqi∈Qby constructing isomorphic triangulations ofPandQ. These isomorphic triangulations consist ofO(M log n+n log2 n) triangles whereMis the size of the optimal (minimum size) solution. The algorithm runs inO(M log n+n log2 n) time. We also give anO(n+L+k log k) algorithm for constructingkpairwise disjoint interior paths betweenkpairs of vertices in a simple polygon onnvertices usingO(L+k log k) links. The numberLis the sum of the interior link distances between thekpairs of vertices.