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 -