Approximating the Maximum Overlap of Polygons under
Translation
Sariel Har-Peled
and
Subhro Roy.
Let $P$ and $Q$ be two simple polygons in the plane of
total complexity $n$, each of which can be decomposed into at most
$k$ convex parts. We present an $(1-\varepsilon)$-approximation
algorithm, for finding the translation of $Q$, which
maximizes its area of overlap with $P$. Our algorithm runs in
$O( c n \log n)$ time, where $c$ is a constant that depends
only on $k$ and $\varepsilon$.
This suggest that for polygons that are ``close'' to being convex,
the problem can be solved (approximately), in near linear time.
PDF.
Last modified: Wed Jan 22 16:16:29 CST 2014