Article

An optimal generalization of the centerpoint theorem, and its extensions

Authors:

Saurabh Ray,

Nabil MustafaAuthors Info & Claims

SCG '07: Proceedings of the twenty-third annual symposium on Computational geometry

Pages 138 - 141

https://doi.org/10.1145/1247069.1247097

Published: 06 June 2007 Publication History

Get Access

Abstract

We prove an optimal generalization of the centerpoint theorem: given a set P of n points in the plane, there exist two points (not necessarily among input points) that hit allconvex objects containingmore than 4n/7 points of P. We further prove that this bound is tight. We get this bound as part of a more general procedure forfinding small number of points hitting convex sets over P, yieldingseveral improvements over previous results.

References

[1]

Noga Alon, Imre Bárány, Zoltán Füredi, and Daniel J. Kleitman. Point selections and weak e-nets for convex hulls. Combinatorics, Probability & Computing, 1:189--200, 1992.

Crossref

Google Scholar

[2]

B. Aronov, F. Aurenhammer, F. Hurtado, S. Langerman, D. Rappaport, S. Smorodinsky, and C. Seara. Small weak epsilon nets. In Proc. 17th Canadian Conference on Computational Geometry, 2005.

Google Scholar

[3]

Bernard Chazelle, Herbert Edelsbrunner, Michelangelo Grigni, Leonidas Guibas, Micha Sharir, and Emo Welzl. Improved bounds on weak eps-nets for convex sets. In Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, pages 495--504, 1993.

Digital Library

Google Scholar

[4]

Kenneth L. Clarkson, David Eppstein, Gary L. Miller, Carl Sturtivant, and Shang-Hua Teng. Approximating center points with iterative radon points. Int. J. Comput. Geometry Appl, 6(3):357--377, 1996.

Crossref

Google Scholar

[5]

D.L. Donoho and M. Gasko. Breakdown properties of location estimates based on halfspace depth and projected outlyingness. The Annals of Statistics, 20:1803--1827, 1994.

Crossref

Google Scholar

[6]

Jirí Matousek. Lectures in Discrete Geometry. Springer-Verlag, New York, NY, 2002.

Digital Library

Google Scholar

[7]

Jirí Matousek and Uli Wagner. New constructions of weak epsilon-nets. Discrete & Computational Geometry, 32(2):195--206, 2004.

Digital Library

Google Scholar

[8]

G. Miller, S. Teng, WThurston, and S.A. Vavasis. Automatic mesh partitioning. Workshop on Sparse Matrix Computations: Graph Theory Issues and Algorithms, 1993.

Crossref

Google Scholar

[9]

Gary L. Miller, Shang-Hua Teng, William P. Thurston, and Stephen A. Vavasis. Separators for sphere-packings and nearest neighbor graphs. Journal of ACM, 44:1--29, 1997.

Digital Library

Google Scholar

[10]

Janos Pach and Pankaj K. Agarwal. Combinatorial Geometry. John Wiley & Sons, New York, NY, 1995.

Crossref

Google Scholar

[11]

F. Frances Yao. A 3-space partition and its applications. In Proceedings of the fifteenth annual ACM symposium on Theory of computing, pages 258--263, 1983.

Digital Library

Google Scholar

Cited By

View all

Lee CAbbas W(2024)A Geometric Approach to Resilient Distributed Consensus Accounting for State Imprecision and Adversarial Agents2024 American Control Conference (ACC)10.23919/ACC60939.2024.10644219(220-225)Online publication date: 10-Jul-2024
https://doi.org/10.23919/ACC60939.2024.10644219
Basit AMustafa NRay SRaza S(2010)Centerpoints and Tverberg's techniqueComputational Geometry: Theory and Applications10.1016/j.comgeo.2010.03.00243:6-7(593-600)Online publication date: 1-Aug-2010
https://dl.acm.org/doi/10.1016/j.comgeo.2010.03.002
Aronov BAurenhammer FHurtado FLangerman SRappaport DSeara CSmorodinsky S(2009)Small weak epsilon-netsComputational Geometry: Theory and Applications10.1016/j.comgeo.2008.02.00542:5(455-462)Online publication date: 1-Jul-2009
https://dl.acm.org/doi/10.1016/j.comgeo.2008.02.005

Index Terms

An optimal generalization of the centerpoint theorem, and its extensions
1. Theory of computation
  1. Randomness, geometry and discrete structures
    1. Computational geometry

Recommendations

An optimal extension of the centerpoint theorem

We prove an optimal extension of the centerpoint theorem: given a set P of n points in the plane, there exist two points (not necessarily among input points) that hit all convex sets containing more than 47n points of P. We further prove that this bound ...
Convex hulls of spheres and convex hulls of disjoint convex polytopes

Given a set @S of spheres in E^d, with d>=3 and d odd, having a constant number of m distinct radii @r"1,@r"2,...,@r"m, we show that the worst-case combinatorial complexity of the convex hull of @S is @Q(@__ __"1"=<"i"<>"j"=<"mn"in"j^@__ __^d^2^@__ __), ...
Convex hulls of spheres and convex hulls of convex polytopes lying on parallel hyperplanes
SoCG '11: Proceedings of the twenty-seventh annual symposium on Computational geometry

Given a set Σ of spheres in E^d, with d≥3 and d odd, having a fixed number of m distinct radii ρ₁,ρ₂,...,ρ_m, we show that the worst-case combinatorial complexity of the convex hull CH_d(Σ) of Σ is Θ(Σ_{{1≤i≠j≤m}}n_in_j^{⌊ d/2 ⌋}), where n_i is the number of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SCG '07: Proceedings of the twenty-third annual symposium on Computational geometry

June 2007

404 pages

ISBN:9781595937056

DOI:10.1145/1247069

Program Chair:
Jeff Erickson
University of Illinois, Urbana-Champaign, USA

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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 June 2007

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
260
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 18 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Lee CAbbas W(2024)A Geometric Approach to Resilient Distributed Consensus Accounting for State Imprecision and Adversarial Agents2024 American Control Conference (ACC)10.23919/ACC60939.2024.10644219(220-225)Online publication date: 10-Jul-2024
https://doi.org/10.23919/ACC60939.2024.10644219
Basit AMustafa NRay SRaza S(2010)Centerpoints and Tverberg's techniqueComputational Geometry: Theory and Applications10.1016/j.comgeo.2010.03.00243:6-7(593-600)Online publication date: 1-Aug-2010
https://dl.acm.org/doi/10.1016/j.comgeo.2010.03.002
Aronov BAurenhammer FHurtado FLangerman SRappaport DSeara CSmorodinsky S(2009)Small weak epsilon-netsComputational Geometry: Theory and Applications10.1016/j.comgeo.2008.02.00542:5(455-462)Online publication date: 1-Jul-2009
https://dl.acm.org/doi/10.1016/j.comgeo.2008.02.005

View Options

Login options

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

Cited By

Index Terms

Recommendations

An optimal extension of the centerpoint theorem

Convex hulls of spheres and convex hulls of disjoint convex polytopes

Convex hulls of spheres and convex hulls of convex polytopes lying on parallel hyperplanes