A non-linear lower bound for planar epsilon-nets

Noga Alon

doi:10.1109/FOCS.2010.39

A non-linear lower bound for planar epsilon-nets

Noga Alon

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

7 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 in 1990.

Original language	English (US)
Title of host publication	Proceedings - 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS 2010
Publisher	IEEE Computer Society
Pages	341-346
Number of pages	6
ISBN (Print)	9780769542447
DOIs	https://doi.org/10.1109/FOCS.2010.39
State	Published - 2010
Externally published	Yes
Event	2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS 2010 - Las Vegas, United States Duration: Oct 23 2010 → Oct 26 2010

Publication series

Name	Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
ISSN (Print)	0272-5428

Conference

Conference	2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS 2010
Country/Territory	United States
City	Las Vegas
Period	10/23/10 → 10/26/10

All Science Journal Classification (ASJC) codes

General Computer Science

Keywords

Epsilon nets
VC dimension
Weak epsilon nets

Access to Document

10.1109/FOCS.2010.39

Cite this

@inproceedings{20efd472b66a4fd7ba5dba1f62d35d77,

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 in 1990.",

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

author = "Noga Alon",

year = "2010",

doi = "10.1109/FOCS.2010.39",

language = "English (US)",

isbn = "9780769542447",

series = "Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS",

publisher = "IEEE Computer Society",

pages = "341--346",

booktitle = "Proceedings - 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS 2010",

address = "United States",

note = "2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS 2010 ; Conference date: 23-10-2010 Through 26-10-2010",

}

Alon, N 2010, A non-linear lower bound for planar epsilon-nets. in Proceedings - 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS 2010., 5671197, Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS, IEEE Computer Society, pp. 341-346, 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS 2010, Las Vegas, United States, 10/23/10. https://doi.org/10.1109/FOCS.2010.39

A non-linear lower bound for planar epsilon-nets. / Alon, Noga.
Proceedings - 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS 2010. IEEE Computer Society, 2010. p. 341-346 5671197 (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - A non-linear lower bound for planar epsilon-nets

AU - Alon, Noga

PY - 2010

Y1 - 2010

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 in 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 in 1990.

KW - Epsilon nets

KW - VC dimension

KW - Weak epsilon nets

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

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

U2 - 10.1109/FOCS.2010.39

DO - 10.1109/FOCS.2010.39

M3 - Conference contribution

AN - SCOPUS:78751549650

SN - 9780769542447

T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

SP - 341

EP - 346

BT - Proceedings - 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS 2010

PB - IEEE Computer Society

T2 - 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS 2010

Y2 - 23 October 2010 through 26 October 2010

ER -

A non-linear lower bound for planar epsilon-nets

Abstract

Publication series

Conference

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this