Improved Bounds on Weak ϵ-Nets for Convex Sets

Bernard Chazelle, Herbert Edelsbruiiner, Michelangelo Grigni, Leonidas Guibas, Micha Shari, Emo Welzl

Research output: Chapter in Book/Report/Conference proceedingConference contribution

12 Scopus citations

Abstract

Let S be a set of n points in R, . A set W is a weak e-net for (convex ranges of) S if for any T C S containing en points, the convex hull of T intersects W. We show the existence of weak ϵ-nets of size O (1/ϵdlogβd1/ϵ), where β2 = 0, β3 = 1, and βd ≈0.149 . 2d-1!, improving a previous bound of Alon et al. We present a deterministic algorithm for computing such a net in time (1/ϵ)O(1). We also consider two special cases: When S is a planar point set in convex position, we prove the existence of a net of size 0(1/ϵ log 1.6 1/ϵ). In the case where S consists of the vertices of a regular polygon, we use an argument from hyperbolic geometry to exhibit an optimal net of size 0(l/ϵ), which improves a previous bound of Capoyleas.

Original languageEnglish (US)
Title of host publicationProceedings of the 25th Annual ACM Symposium on Theory of Computing, STOC 1993
PublisherAssociation for Computing Machinery
Pages495-504
Number of pages10
ISBN (Electronic)0897915917
DOIs
StatePublished - Jun 1 1993
Event25th Annual ACM Symposium on Theory of Computing, STOC 1993 - San Diego, United States
Duration: May 16 1993May 18 1993

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
VolumePart F129585
ISSN (Print)0737-8017

Other

Other25th Annual ACM Symposium on Theory of Computing, STOC 1993
CountryUnited States
CitySan Diego
Period5/16/935/18/93

All Science Journal Classification (ASJC) codes

  • Software

Fingerprint Dive into the research topics of 'Improved Bounds on Weak ϵ-Nets for Convex Sets'. Together they form a unique fingerprint.

Cite this