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:








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



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
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
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 02:12:27 PM
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