Proceedings Article, Paper @InProceedings Beitrag in Tagungsband, Workshop

 Show entries of: this year (2019) | last year (2018) | two years ago (2017) | Notes URL
 Action: login to update Options: Goto entry point

 Author, Editor
 Author(s): Ray, Saurabh Mustafa, Nabil H. dblp dblp Not MPG Author(s): Ray, Saurabh
 Editor(s):
 BibTeX cite key*: NaRa07b

 Title, Booktitle
 Title*: Weak $\epsilon$-nets have a basis of size $O(1/\epsilon\log 1/\epsilon)$ in any dimension Booktitle*: Proceedings of the Twenty-Third Annual Symposium on Computational Geometry (SCG'07)

 Event, URLs
 URL of the conference: http://www.socg.org/2007/ URL for downloading the paper: http://delivery.acm.org/10.1145/1250000/1247113/p239-ray.pdf?key1=1247113&key2=8143392811&coll=GUIDE&dl=GUIDE&CFID=22430507&CFTOKEN=31336734 Event Address*: Gyeongju, South Korea Language: English Event Date* (no longer used): Organization: Association for Computing Machinery (ACM) Event Start Date: 6 June 2007 Event End Date: 8 June 2007

 Publisher
 Name*: ACM URL: http://www.acm.org/ Address*: New York, NY, USA Type:

 Vol, No, Year, pp.
 Series:
 Volume: Number: Month: Pages: 239-244 Year*: 2007 VG Wort Pages: ISBN/ISSN: 978-1-59593-705-6 Sequence Number: DOI: 10.1145/1247069.1247113

 (LaTeX) Abstract: Given a set P of n points in Rd and $\epsilon$ > 0, we consider the problem of constructing weak $\epsilon$-nets for P. We show the following: pick a random sample Q of size O(1/$\epsilon$ log (1/$\epsilon$)) from P. Then, with constant probability, a weak $\epsilon$-net of P can be constructed from only the points of Q. This shows that weak $\epsilon$-nets in Rd can be computed from a subset of P of size O(1/$\epsilon$ log (1/$\epsilon$)) with only the constant of proportionality depending on the dimension, unlike all previous work where the size of the subset had the dimension in the exponent of 1/$\epsilon$. However, our final weak $\epsilon$-nets still have a large size (with the dimension appearing in the exponent of 1/$\epsilon$). URL for the Abstract: http://portal.acm.org/citation.cfm?doid=1247069.1247113 Personal Comments: Weak ε-nets have basis of size o(1/ε log (1/ε)) in any dimension Download Access Level: Internal

 Correlation
 MPG Unit: Max-Planck-Institut für Informatik MPG Subunit: Algorithms and Complexity Group Appearance: MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort

BibTeX Entry:

@INPROCEEDINGS{NaRa07b,
AUTHOR = {Ray, Saurabh and Mustafa, Nabil H.},
TITLE = {Weak $\epsilon$-nets have a basis of size ${O}(1/\epsilon\log 1/\epsilon)$ in any dimension},
BOOKTITLE = {Proceedings of the Twenty-Third Annual Symposium on Computational Geometry (SCG'07)},
PUBLISHER = {ACM},
YEAR = {2007},
ORGANIZATION = {Association for Computing Machinery (ACM)},
PAGES = {239--244},