Bounded boxes, Hausdorff distance, and a new proof of an interesting Helly-type theorem

ABSTRACT

In the first part of this paper, we reduce two geometric optimization problems to convex programming: finding the largest axis-aligned box in the intersection of a family of convex sets, and finding the translation and scaling that minimizes the Hausdorff distance between two polytopes. These reductions imply that important cases of these problems can be solved in expected linear time. In the second part of the paper, we use convex programming to give a new, short proof of an interesting Helly-type theorem, first conjectured by Gru¨nbaum and Motzkin.

REFERENCES

• A93: Nina Amenta, Helly theorems and generalized linear programming, Proceedings of the ninth annual symposium on Computational geometry, p.63-72, May 18-21, 1993, San Diego, California, United States [doi>10.1145/160985.161000]
• A93': Annamaria Beatrice Amenta, Helly theorems and generalized linear programming, University of California at Berkeley, Berkeley, CA, 1995
• ABB91: Helmut Alt , Bernd Behrends , Johannes Blömer, Approximate matching of polygonal shapes (extended abstract), Proceedings of the seventh annual symposium on Computational geometry, p.186-193, June 10-12, 1991, North Conway, New Hampshire, United States [doi>10.1145/109648.109669]
• AK89: James Arvo , David Kirk, A survey of ray tracing acceleration techniques, An introduction to ray tracing, Academic Press Ltd., London, UK, 1989
• A83: Mikhail J. AtaUah. A linear time algorithm for the Hausdorff distance between convex polygons, Information Processing Letters 17 (1983), pages 207-9.
• CGHKKK94: L. Paul Chew, Michael T. Goodrich, Daniel P. Huttenlocher, Klara Kedem, Jon M. Kleinberg, and Dina Kravets. Geometric Pattern Matching under Euclidean Motion, Proceedings of the Fifth Canadian Conference on Computational Geometry, (1993) pages 151-156
• C90: Kenneth L. Clarkson. Las Vegas algorithms for linear and integer programming when the dimension is small, manuscript, 1990. An earlier version appeared in Proceedings of the 29th Annual Symposium on Foundations of Computer Science, pages 452-5, 1988.
• DMR93: Karen Daniels, Victor Milenkovic and Dan Roth. Finding the maximum area axis-parallel rectangle in a polygon, Proceedings of the Fifth Canadian Conference on Computational Geometry, (1993) pages 322- 327.
• DGK63: Ludwig Danzer, Branko Gr/inbaum, and Victor Klee. Helly's Theorem and it's relatives, Proceedings of the Symposium on Pure Mathematics, Vol. 7, Convexity (1963) pages 101- 180. American Mathematical Society, Providence, RI.
• E93: Jfirgen Eckhoff. Helly, Radon and Carathody type theorems, Chapter 2.1 in Handbook of Convex Geometry, P.M. Gruber and J.M. Willis, eds., (1993) Elsevier Science Publishers B. V., Amsterdam.
• GM61: Branko Grfinbaum and Theodore S. Motzkin. On components in some families of sets, Proceedings of the American Mathematical Society, vol. 12, (1961) pages 607-613.
• HKS91: Daniel P. Huttenlocher , Klara Kedem , Micha Sharir, The upper envelope of Voronoi surfaces and its applications, Proceedings of the seventh annual symposium on Computational geometry, p.194-203, June 10-12, 1991, North Conway, New Hampshire, United States [doi>10.1145/109648.109670]
• L68: D.G. Larman. Helly type properties of unions of convex sets, Mathematika 15 (1968) pages 53-59.
• M94: Jiří Matoušek, On geometric optimization with few violated constraints, Proceedings of the tenth annual symposium on Computational geometry, p.312-321, June 06-08, 1994, Stony Brook, New York, United States [doi>10.1145/177424.178039]
• MSW92: Jiří Matoušek , Micha Sharir , Emo Welzl, A subexponential bound for linear programming, Proceedings of the eighth annual symposium on Computational geometry, p.1-8, June 10-12, 1992, Berlin, Germany [doi>10.1145/142675.142678]
• Mo73: Howard Caxy Morris. Two Pigeon Hole Principles and Unions of Convexly Disjoint Sets, PhD thesis, California Institute of Technology, Pasadena, California (1973).
• S90: Raimund Seidel, Linear programming and convex hulls made easy, Proceedings of the sixth annual symposium on Computational geometry, p.211-215, June 07-09, 1990, Berkley, California, United States [doi>10.1145/98524.98570]
• SW92: Micha Sharir , Emo Welzl, A Combinatorial Bound for Linear Programming and Related Problems, Proceedings of the 9th Annual Symposium on Theoretical Aspects of Computer Science, p.569-579, February 13-15, 1992
• W91: Emo Welzl. Smallest enclosing disks (balls a~d ~llipgoidg), T~ehnieal vport number B 91-09 Fachbereich Mathematik, Freie Universit/it Berlin, Berlin, Germany (1991)

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Linear programming
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms

General Terms:
Algorithms, Theory, Verification