MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

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
Conference URL::
http://www.socg.org/2007/
Downloading URL:
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
Note, Abstract, ©
(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},
 ADDRESS = {Gyeongju, South Korea},
 ISBN = {978-1-59593-705-6},
 DOI = {10.1145/1247069.1247113},
}

Entry last modified by Uwe Brahm, 02/28/2008
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Stefan Funke		Created
03/20/2007 14:12:27
Revisions
6.
5.
4.
3.
2.		Editor(s)
Uwe Brahm
Uwe Brahm
Christine Kiesel
Christine Kiesel
Christine Kiesel		Edit Dates
2007-07-18 14:43:54
07/07/2007 00:43:21
27.06.2007 11:04:49
27.06.2007 10:48:40
03/20/2007 02:39:15 PM