TY - GEN

T1 - Improved Bounds on Weak ϵ-Nets for Convex Sets

AU - Chazelle, Bernard

AU - Edelsbruiiner, Herbert

AU - Grigni, Michelangelo

AU - Guibas, Leonidas

AU - Shari, Micha

AU - Welzl, Emo

N1 - Publisher Copyright:
© 1993 ACM.

PY - 1993/6/1

Y1 - 1993/6/1

N2 - 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.

AB - 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.

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

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

U2 - 10.1145/167088.167222

DO - 10.1145/167088.167222

M3 - Conference contribution

AN - SCOPUS:0027150669

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 495

EP - 504

BT - Proceedings of the 25th Annual ACM Symposium on Theory of Computing, STOC 1993

PB - Association for Computing Machinery

T2 - 25th Annual ACM Symposium on Theory of Computing, STOC 1993

Y2 - 16 May 1993 through 18 May 1993

ER -