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):

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

URL of the conference:

http://www.umiacs.umd.edu/conferences/socg2008/

URL for downloading the paper:

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
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)
Evangelia Pyrga
Created
02/12/2009 12:38:11 PM
Revision
0.



Editor
Evangelia Pyrga



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



Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section