Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. Tight lower bounds for the size of epsilon-nets
 
conference paper

Tight lower bounds for the size of epsilon-nets

Pach, János  
•
Tardos, Gábor
2011
SoCG '11: Proceedings of the twenty-seventh annual symposium on Computational geometry
27th Annual ACM Symposium on Computational Geometry

According to a well known theorem of Haussler and Welzl (1987), any range space of bounded VC-dimension admits an epsilon-net of size O (1/epsilon log 1/epsilon). Using probabilistic techniques, Pach and Woeginger (1990) showed that there exist range spaces of VC-dimension 2, for which the above bound is sharp. The only known range spaces of small VC-dimension, in which the ranges are geometric objects in some Euclidean space and the size of the smallest epsilon-nets is superlinear in 1/epsilon, were found by Alon (2010). In his examples, every epsilon-net is of size Omega (1/epsilon g(1/epsilon)), where g is an extremely slowly growing function, related to the inverse Ackermann function.

  • Details
  • Metrics
Type
conference paper
DOI
10.1145/1998196.1998271
Web of Science ID

WOS:000292906900058

Author(s)
Pach, János  
Tardos, Gábor
Date Issued

2011

Publisher

Acm Order Department, P O Box 64145, Baltimore, Md 21264 Usa

Published in
SoCG '11: Proceedings of the twenty-seventh annual symposium on Computational geometry
Start page

458

End page

463

Subjects

Axis-Parallel Rectangles

•

Hales-Jewett Theorem

•

Density Version

•

Vc-Dimension

•

Boxes

•

Sets

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
DCG  
Event nameEvent place
27th Annual ACM Symposium on Computational Geometry

Paris, France

Available on Infoscience
December 12, 2011
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/73121
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés