A non-linear lower bound for planar epsilon-nets

被引：4
作者：
Alon, Noga [1 ]
机构：
[1] Tel Aviv Univ, Sch Math, IL-69978 Tel Aviv, Israel
来源：
2010 IEEE 51ST ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE | 2010年
基金：
美国国家科学基金会;
关键词：
Epsilon nets; weak epsilon nets; VC dimension; DENSITY VERSION;
D O I：
10.1109/FOCS.2010.39
中图分类号：
TP31 [计算机软件];
学科分类号：
081202 ; 0835 ;
摘要：
We show that the minimum possible size of an epsilon-net for point objects and line (or rectangle)-ranges in the plane is (slightly) bigger than linear in 1 / epsilon. This settles a problem raised by Matousek, Seidel and Welzl in 1990.
引用
收藏
页码：341 / 346
页数：6
相关论文
共 36 条
[1]   PARTITIONING ARRANGEMENTS OF LINES .2. APPLICATIONS [J].
AGARWAL, PK .
DISCRETE & COMPUTATIONAL GEOMETRY, 1990, 5 (06) :533-573
[2]   PARTITIONING ARRANGEMENTS OF LINES .1. AN EFFICIENT DETERMINISTIC ALGORITHM [J].
AGARWAL, PK .
DISCRETE & COMPUTATIONAL GEOMETRY, 1990, 5 (05) :449-483
[3]   Transversal numbers for hypergraphs arising in geometry [J].
Alon, N ;
Kalai, G ;
Matousek, J ;
Meshulam, R .
ADVANCES IN APPLIED MATHEMATICS, 2002, 29 (01) :79-101
[4]  
Alon N, 2008, PROBABILISTIC METHOD
[5]  
Alon N., 1987, P 3 ANN S COMP GEOM, P331, DOI 10.1145/41958.41994
[6]  
[Anonymous], 1994, BOLYAI SOC MATH STUD
[7]  
[Anonymous], 2002, GRAD TEXT M, DOI 10.1007/978-1-4613-0039-7
[8]  
Aronov B., P STOC 09, P639
[9]   ALMOST OPTIMAL SET COVERS IN FINITE VC-DIMENSION [J].
BRONNIMANN, H ;
GOODRICH, MT .
DISCRETE & COMPUTATIONAL GEOMETRY, 1995, 14 (04) :463-479
[10]   Lower Bounds for Weak Epsilon-Nets and Stair-Convexity [J].
Bukh, Boris ;
Matousek, Jiri ;
Nivasch, Gabriel .
PROCEEDINGS OF THE TWENTY-FIFTH ANNUAL SYMPOSIUM ON COMPUTATIONAL GEOMETRY (SCG'09), 2009, :1-10
1234