MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Pyrga, Evangelia
Ray, Saurabh
dblp
dblp
Not MPG Author(s):
Ray, Saurabh
Editor(s):
BibTeX cite key*:
Pyrga2008
Title, Booktitle
Title*:
New existence Proofs for epsilon-nets
Booktitle*:
Proceedings of the twenty-fourth annual symposium on Computational geometry
Event, URLs
Conference URL::
http://www.umiacs.umd.edu/conferences/socg2008/
Downloading URL:
http://portal.acm.org/citation.cfm?id=1377708
Event Address*:
College Park, MD, USA
Language:
English
Event Date*
(no longer used):
Organization:
Association for Computing Machinery (ACM)
Event Start Date:
9 June 2008
Event End Date:
11 June 2008
Publisher
Name*:
ACM
URL:
http://www.acm.org/publications
Address*:
New York, USA
Type:
Vol, No, Year, pp.
Series:
Volume:
Number:
Month:
Pages:
199-207
Year*:
2008
VG Wort Pages:
ISBN/ISSN:
978-1-60558-071-5
Sequence Number:
DOI:
10.1145/1377676.1377708
Note, Abstract, ©
(LaTeX) Abstract:
We describe a new technique for proving the existence of small $\eps$-nets for
hypergraphs satisfying certain simple conditions. The technique is particularlyuseful for proving $o(\frac{1}{\eps}\log{\frac{1}{\eps}})$ upper bounds which
is not possible using the standard VC dimension theory. We apply the technique
to several geometric hypergraphs and obtain simple proofs for the existence of
$O(\frac{1}{\eps})$ size $\eps$-nets for them. This includes the geometric
hypergraph in which the vertex set is a set of points in the plane and the
hyperedges are defined by a set of pseudo-disks. This result was not known
previously. We also get a very short proof for the existence of $O(\frac{1}{\eps})$ size
$\eps$-nets for half\-spaces in $\Re^3$.
URL for the Abstract:
http://portal.acm.org/citation.cfm?doid=1377676.1377708
Keywords:
Discrete Geometry, Strong -nets, Hitting Sets, Hypergraph Transversals
Download
Access Level:
Public

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



BibTeX Entry:

@INPROCEEDINGS{Pyrga2008,
AUTHOR = {Pyrga, Evangelia and Ray, Saurabh},
TITLE = {New existence Proofs for epsilon-nets},
BOOKTITLE = {Proceedings of the twenty-fourth annual symposium on Computational geometry},
PUBLISHER = {ACM},
YEAR = {2008},
ORGANIZATION = {Association for Computing Machinery (ACM)},
PAGES = {199--207},
ADDRESS = {College Park, MD, USA},
ISBN = {978-1-60558-071-5},
DOI = {10.1145/1377676.1377708},
}


Entry last modified by Evangelia Pyrga, 03/03/2009
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)
Evangelia Pyrga
Created
02/12/2009 12:38:11 PM
Revision
0.



Editor
Evangelia Pyrga



Edit Date
02/12/2009 12:38:11 PM