# MPI-I-91-105

## Simultaneous inner and outer aproximation of shapes

### Fleischer, Rudolf and Mehlhorn, Kurt and Rote, Günter and Welzl, Emo

**MPI-I-91-105**. May** **1991, 24 pages. | Status:** **available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:

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.

Acknowledgement:** **

References to related material:

To download this research report, please select the type of document that fits best your needs. | Attachement Size(s): |

| 12738 KBytes |

Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView |

**URL to this document: **http://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},`

`}`