DIMACS TR: 94-52

Constructing Piecewise Linear Hemomorphisms



Authors: Diane Souvaine and Rephael Wenger

ABSTRACT

Let $P = \{p_1,\ldots,p_n\}$ and $Q = \{q_1,\ldots,q_n\}$ be two point sets lying in the interior of rectangles in the plane. We show how to construct a piecewise linear homeomorphism of size $O(n^2)$ between the rectangles which maps $p_i$ to $q_i$ for each $i$. This bound is optimal in the worst case; i.e., there exist point sets for which any piecewise linear homeomorphism has size $\Omega(n^2)$.

Paper available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1994/94-52.ps
DIMACS Home Page