A Non-linear Lower Bound for Planar Epsilon-nets

Noga Alon

doi:10.1007/s00454-010-9323-7

A Non-linear Lower Bound for Planar Epsilon-nets

Noga Alon

Research output: Contribution to journal › Article › peer-review

29 Scopus citations

Abstract

We show that the minimum possible size of an ε-net for point objects and line (or rectangle)-ranges in the plane is (slightly) bigger than linear in 1/ε. This settles a problem raised by Matoušek, Seidel and Welzl (Proc. 6th Annu. ACM Sympos. Comput. Geom., pp. 16-22, 1990).

Original language	English (US)
Pages (from-to)	235-244
Number of pages	10
Journal	Discrete and Computational Geometry
Volume	47
Issue number	2
DOIs	https://doi.org/10.1007/s00454-010-9323-7
State	Published - Mar 2012
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Geometry and Topology
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Keywords

Epsilon nets
VC-dimension
Weak epsilon nets

Access to Document

10.1007/s00454-010-9323-7

Cite this

@article{f6da4b7472414285938dc4389a282ce3,

title = "A Non-linear Lower Bound for Planar Epsilon-nets",

abstract = "We show that the minimum possible size of an ε-net for point objects and line (or rectangle)-ranges in the plane is (slightly) bigger than linear in 1/ε. This settles a problem raised by Matou{\v s}ek, Seidel and Welzl (Proc. 6th Annu. ACM Sympos. Comput. Geom., pp. 16-22, 1990).",

keywords = "Epsilon nets, VC-dimension, Weak epsilon nets",

author = "Noga Alon",

year = "2012",

month = mar,

doi = "10.1007/s00454-010-9323-7",

language = "English (US)",

volume = "47",

pages = "235--244",

journal = "Discrete and Computational Geometry",

issn = "0179-5376",

publisher = "Springer New York",

number = "2",

}

TY - JOUR

T1 - A Non-linear Lower Bound for Planar Epsilon-nets

AU - Alon, Noga

PY - 2012/3

Y1 - 2012/3

N2 - We show that the minimum possible size of an ε-net for point objects and line (or rectangle)-ranges in the plane is (slightly) bigger than linear in 1/ε. This settles a problem raised by Matoušek, Seidel and Welzl (Proc. 6th Annu. ACM Sympos. Comput. Geom., pp. 16-22, 1990).

AB - We show that the minimum possible size of an ε-net for point objects and line (or rectangle)-ranges in the plane is (slightly) bigger than linear in 1/ε. This settles a problem raised by Matoušek, Seidel and Welzl (Proc. 6th Annu. ACM Sympos. Comput. Geom., pp. 16-22, 1990).

KW - Epsilon nets

KW - VC-dimension

KW - Weak epsilon nets

UR - http://www.scopus.com/inward/record.url?scp=84855590895&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84855590895&partnerID=8YFLogxK

U2 - 10.1007/s00454-010-9323-7

DO - 10.1007/s00454-010-9323-7

M3 - Article

AN - SCOPUS:84855590895

SN - 0179-5376

VL - 47

SP - 235

EP - 244

JO - Discrete and Computational Geometry

JF - Discrete and Computational Geometry

IS - 2

ER -

A Non-linear Lower Bound for Planar Epsilon-nets

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this