Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop
Show entries of:
this year
(2020) |
last year
(2019) |
two years ago
(2018) |
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
Note, Abstract, ©
(LaTeX) Abstract:
Given a set
P
of
n
points in
R
d
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
R
d
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
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