## 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