MPI-I-91-105
Simultaneous inner and outer aproximation of shapes
Fleischer, Rudolf and Mehlhorn, Kurt and Rote, Günter and Welzl, Emo
May 1991, 24 pages.
.
Status: available - back from printing
For compact Euclidean bodies $P,Q$, we define $\lambda(P,Q)$
to be the smallest ratio $r/s$ where $r > 0$, $s > 0$ satisfy
$sQ' \subseteq P \subseteq$ $rQ''$. Here $sQ$
denotes a scaling of $Q$ by factor $s$, and $Q', Q''$
are some translates of $Q$. This function $\lambda$ gives us a
new distance function between bodies wich, unlike previously studied
measures, is invariant under affine transformations. If homothetic
bodies are identified, the logarithm of this function is a metric.
(Two bodies are {\sl homothetic} if one can be obtained from the other
by scaling and translation).
For integer $ k\geq3 $, define $\lambda(k)$ to be the minimum value
such that for each convex polygon $P$ there exists a convex $k$-gon
$Q$ with $\lambda(P,Q) \leq$ $\lambda(k)$. Among other
results, we prove that $ 2.118\ldots\leq\lambda(3)\leq 2.25 $
and $\lambda(k) = 1 + \Theta(k^{-2}) $. We give an $ O(n^2 log^2 n) $
time algorithm which for any input convex $n$-gon $P$, finds
a triangle $T$ that minimizes $\lambda(T,P)$ among triangles.
But in linear time, we can find a triangle $t$ with
$\lambda(t,P) \leq$ $2.25$.
Our study is motivated by the attempt to reduce the complexity
of the polygon containment problem, and also the motion planning
problem. In each case, we describe algorithms wich will run faster
when certain implicit {\sl slackness} parameters of the input
are bounded away from 1. These algorithms illustrate a new algorithmic
paradigm in computational geometry for coping with complexity.
-
- Attachement: MPI-I-91-105.pdf (12738 KBytes)
URL to this document: https://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1991-105
BibTeX
@TECHREPORT{FleischerMehlhornRoteWelzl91,
AUTHOR = {Fleischer, Rudolf and Mehlhorn, Kurt and Rote, G{\"u}nter and Welzl, Emo},
TITLE = {Simultaneous inner and outer aproximation of shapes},
TYPE = {Research Report},
INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
NUMBER = {MPI-I-91-105},
MONTH = {May},
YEAR = {1991},
ISSN = {0946-011X},
}