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

# 1. On spontaneous inner and outer approximation of shapes

In: *Proceedings of the Sixth Annual Symposium on Computational
Geometry, Berkeley, California, June 6–8, 1990*. Association
for Computing Machinery, 1990; pp. 216–224. doi:10.1145/98524.98572
# 2. Simultaneous inner and outer approximation of shapes

*Algorithmica* **8** (1992), 365–389, (Zbl 760.68083). doi:10.1007/BF01758852
(This is a more detailed version of 1.)
### Abstract

For compact Euclidean bodies `P`, `Q`, we define
λ(`P`,`Q`)
to be the smallest ratio `r`/`s` such
that `P` is contains a translated copy of `Q` scaled
by a positive factor `s` and is contained in a translated copy
of `Q` scaled by a positive factor `r`. This function
λ gives us a new distance function between bodies
which, 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 homothetic if one can be obtained from
the other by scaling and translation.)
For integer `k`≥3, we study `λ`(`k`),
the minimum value such that for each convex polygon `P`
there exists a convex `k`-gon `Q` with
λ(`P`,`Q`)≤`λ`(`k`).
Among other
results, we prove that 2.118...≤λ(3)≤2.25 and
λ(`k`) = 1 + Θ(1/`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
λ(`T`,`P`) among triangles. However, in linear time we
can find a triangle `T` with
λ(`T`,`P`)≤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 which run faster when certain implicit slackness
parameters of the input are bounded away from 1. These algorithms illustrate
a new algorithmic paradigm in computational geometry for coping with
complexity.

Last update: August 15, 2017.