Simultaneous inner and outer approximation of shapes

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

Research output: Contribution to journalArticle


For compact Euclidean bodies P, Q, we define λ(P, Q) to be the smallest ratio r/s where r > 0, s > 0 satisfy {Mathematical expression}. Here sQ denotes a scaling of Q by the factor s, and Q′, Q″ are some translates of Q. 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, define λ(k) to be 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 + Θ(k-2). 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.

Original languageEnglish (US)
Pages (from-to)365-389
Number of pages25
Issue number1
StatePublished - Jan 1992


  • Algorithmic paradigms
  • Banach-Mazur metric
  • Computational geometry
  • Implicit complexity parameters
  • Polygonal approximation
  • Shape approximation

ASJC Scopus subject areas

  • Computer Science(all)
  • Computer Science Applications
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Simultaneous inner and outer approximation of shapes'. Together they form a unique fingerprint.

  • Cite this

    Fleischer, R., Mehlhorn, K., Rote, G., Welzl, E., & Yap, C. (1992). Simultaneous inner and outer approximation of shapes. Algorithmica, 8(1), 365-389.