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.)


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.

  free PDF view@Springer
other papers about this subject
Last update: August 15, 2017.