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/k2).
We give an
O(n2
log2n)-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.