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 - Funding Information:
*Work by Bernard Chazelle has been supported by NSF Grant CCR-90-02352 and the Geometry Center. Work by Herbert Edels-brunner has been supported by NSF Grant CCR-89-21421. Work by Michelangelo Grigni has been supported by NSERC Operating Grants and NSF Grant DMS-9206251. Work by Leonidas Guibas and Micha Sharir has been supported by a grant from the U. S.-Israeli Binational Science Foundation. Work by Emo Welzl and Micha Sharir has been supported by a grant from the G. I. F., the German-Israeli Foundation for Scientific Research and Development. Work by Mkha Sharir has also been supported by NSF Grant CCR-91-22103, and by a grant from the Fired for Basic Research administered by the Israeli Academy of Sciences. Contact Author: chazelle@princeton.edu. t Depmtment of Computer Science, princeton Computer Science Department, Urban&Champaign sDEC Systems Research Science, M. I. T., and Computer University 11School of Mathematical Sciences, Tel Aviv University and Courant Institute of Mathematical Sciences, New York University II~stitut ffi ~omatik, Freie Ufiversitat Berlin

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 -