Article

Free access

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

Author:

Nina AmentaAuthors Info & Claims

SCG '94: Proceedings of the tenth annual symposium on Computational geometry

Pages 340 - 347

https://doi.org/10.1145/177424.178064

Published: 10 June 1994 Publication History

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

[1]

Nina Amenta, Helly Theorems and Generalized Linear Programming, Proceedings of the 7th Annual Symposium on Computational Geometry, (1993) pages 63-72.

Digital Library

[2]

Nina Amenta, Helly Theorems and Generalized Linear Programming (PhD thesis), Geometry Center Technical Report, Number GCG61, (1993).

Digital Library

[3]

Helmut Alt, Bernd Behrends, and Johannes B15mer. Approximate matching of polygonal shapes, Proceedings of the 7th Annual Symposium on Computational Geometry, (1991), pages 186-93.

Digital Library

[4]

James Arvo and David Kirk. A survey of ray tracing acceleration techniques, in An Introduction to Ray Tracing (Andrew Glassner, ed), Academic Press, San Diego, (1989), pages 201-262.

Digital Library

[5]

Mikhail J. AtaUah. A linear time algorithm for the Hausdorff distance between convex polygons, Information Processing Letters 17 (1983), pages 207-9.

[6]

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

[7]

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.

[8]

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.

[9]

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.

[10]

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.

[11]

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.

[12]

Daniel P. Huttenlocher, Klara Kedam and Micha Sharir. The Upper Envelope of Voronoi Surfaces and its Applications, Proceedings of the 7th Annual Symposium on Computational Geometry, (1991) pages 194-203.

Digital Library

[13]

D.G. Larman. Helly type properties of unions of convex sets, Mathematika 15 (1968) pages 53-59.

[14]

Ji~ Matou~ek. On geometric optimization with few violated constraints, These Proceedings.

Digital Library

[15]

Ji~ Matou~ek, Micha Siharir and Emo Welzl. A subexponen~ial bound for linear programming, Proceedings of the 8th Annual Symposium on Computational Geometry (1992) pages 1-8.

Digital Library

[16]

Howard Caxy Morris. Two Pigeon Hole Principles and Unions of Convexly Disjoint Sets, PhD thesis, California Institute of Technology, Pasadena, California (1973).

[17]

Raimund Seidel. Linear programming and convex hulls made easy, Proceedings of the 6th Annual Symposium on Computational Geometry, (1990) pages 211-215.

Digital Library

[18]

Micha Sharir and Emo Welzl. A combinatorial bound for linear programming and related problems, Proceedings of the 9th Annual Symposium on Theoretical Aspects of Computer Science (1992), Lecture Notes in Computer Science 577, pages 569-579.

Digital Library

[19]

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)

Cited By

Messina JSoberón P(2021)Isometric and affine copies of a set in volumetric Helly resultsComputational Geometry10.1016/j.comgeo.2021.101855(101855)Online publication date: Dec-2021
https://doi.org/10.1016/j.comgeo.2021.101855
Lee SEom TAhn H(2021)Largest triangles in a polygonComputational Geometry10.1016/j.comgeo.2021.101792(101792)Online publication date: May-2021
https://doi.org/10.1016/j.comgeo.2021.101792
Choi YLee SAhn H(2020)Maximum-Area and Maximum-Perimeter Rectangles in PolygonsComputational Geometry10.1016/j.comgeo.2020.101710(101710)Online publication date: Sep-2020
https://doi.org/10.1016/j.comgeo.2020.101710
Show More Cited By

Index Terms

Bounded boxes, Hausdorff distance, and a new proof of an interesting Helly-type theorem
1. Mathematics of computing
  1. Discrete mathematics
    1. Combinatorics
      1. Combinatorial algorithms
  2. Mathematical analysis
    1. Mathematical optimization
      1. Continuous optimization
        Linear programming
2. Theory of computation
  1. Design and analysis of algorithms
    1. Mathematical optimization
      1. Continuous optimization
        Linear programming
  2. Randomness, geometry and discrete structures
    1. Computational geometry

Recommendations

A short proof of an interesting helly-type theorem

We give a short proof of the theorem that any family of subsets ofRd, with the property that the intersection of any nonempty finite subfamily can be represented as the disjoint union of at mostk closed convex sets, has Helly number at mostk(d+1).
A Quantitative Helly-Type Theorem: Containment in a Homothet

We introduce a new variant of quantitative Helly-type theorems: the minimal homothetic distance of the intersection of a family of convex sets to the intersection of a subfamily of a fixed size. As an application, we establish the following quantitative ...
A New Topological Helly Theorem and Some Transversal Results

We prove that for a topological space $$X$$ X with the property that $$ H_{*}(U)=0$$ H ( U ) = 0 for $$*\ge d$$ d and every open subset $$U$$ U of $$X$$ X , a finite family of open sets in $$X$$ X has nonempty intersection if for any subfamily of size $$j,\,1\le j\le d+1,$$ j , 1 ≤ j ≤ d + 1 , the $$(d-j)$$ ( d - j ) -dimensional homology group of its intersection is zero. We use ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SCG '94: Proceedings of the tenth annual symposium on Computational geometry

June 1994

400 pages

ISBN:0897916484

DOI:10.1145/177424

Chairman:
Kurt Mehlhorn
U.S. Army Research Office

Copyright © 1994 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 10 June 1994

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

SCG94

Sponsor:

SCG94: Tenth Symposium on Computational Geometry

June 6 - 8, 1994

New York, Stony Brook, USA

Acceptance Rates

Overall Acceptance Rate 625 of 1,685 submissions, 37%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

19
Total Citations
View Citations
563
Total Downloads

Downloads (Last 12 months)58
Downloads (Last 6 weeks)8

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Messina JSoberón P(2021)Isometric and affine copies of a set in volumetric Helly resultsComputational Geometry10.1016/j.comgeo.2021.101855(101855)Online publication date: Dec-2021
https://doi.org/10.1016/j.comgeo.2021.101855
Lee SEom TAhn H(2021)Largest triangles in a polygonComputational Geometry10.1016/j.comgeo.2021.101792(101792)Online publication date: May-2021
https://doi.org/10.1016/j.comgeo.2021.101792
Choi YLee SAhn H(2020)Maximum-Area and Maximum-Perimeter Rectangles in PolygonsComputational Geometry10.1016/j.comgeo.2020.101710(101710)Online publication date: Sep-2020
https://doi.org/10.1016/j.comgeo.2020.101710
Khachatryan AMüller EBöhm KKopper J(2011)Efficient selectivity estimation by histogram construction based on subspace clusteringProceedings of the 23rd international conference on Scientific and statistical database management10.5555/2032397.2032426(351-368)Online publication date: 20-Jul-2011
https://dl.acm.org/doi/10.5555/2032397.2032426
Khachatryan AMüller EBöhm KKopper J(2011)Efficient Selectivity Estimation by Histogram Construction Based on Subspace ClusteringScientific and Statistical Database Management10.1007/978-3-642-22351-8_22(351-368)Online publication date: 2011
https://doi.org/10.1007/978-3-642-22351-8_22
Gärtner BMatoušek JRüst LŠkovroň P(2008)Violator spacesDiscrete Applied Mathematics10.1016/j.dam.2007.08.048156:11(2124-2141)Online publication date: 1-Jun-2008
https://dl.acm.org/doi/10.1016/j.dam.2007.08.048
Gärtner BMatoušek JRüst LŠkovroň P(2006)Violator spacesProceedings of the 14th conference on Annual European Symposium - Volume 1410.1007/11841036_36(387-398)Online publication date: 11-Sep-2006
https://dl.acm.org/doi/10.1007/11841036_36
Agarwal PSharir M(2005)Algorithmic techniques for geometric optimizationComputer Science Today10.1007/BFb0015247(234-253)Online publication date: 9-Jun-2005
https://doi.org/10.1007/BFb0015247
Basri RJacobs D(2005)Matching convex polygons and polyhedra, allowing for occlusionApplied Computational Geometry Towards Geometric Engineering10.1007/BFb0014491(133-147)Online publication date: 9-Jun-2005
https://doi.org/10.1007/BFb0014491
Prabhakar SXia YKalashnikov DAref WHambrusch S(2002)Query Indexing and Velocity Constrained IndexingIEEE Transactions on Computers10.1109/TC.2002.103984051:10(1124-1140)Online publication date: 1-Oct-2002
https://dl.acm.org/doi/10.1109/TC.2002.1039840
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents