Show simple item record

SMALL-SIZE epsilon-NETS FOR AXIS-PARALLEL RECTANGLES AND BOXES

dc.contributor.author Aronov, Boris
dc.contributor.author Ezra, Esther
dc.contributor.author Sharir, Micha
dc.date.accessioned 2011-06-21T17:27:53Z
dc.date.available 2011-06-21T17:27:53Z
dc.date.issued 2010
dc.identifier.citation Aronov,Boris;Ezra,Esther;Sharir,Micha. 2010. SMALL-SIZE epsilon-NETS FOR AXIS-PARALLEL RECTANGLES AND BOXES. Siam Journal on Computing 39(7): 3248-3282.
dc.identifier.issn 0097-5397
dc.identifier.uri https://hdl.handle.net/10161/4313
dc.description.abstract We show the existence of epsilon-nets of size O (1/epsilon log log 1/epsilon) for planar point sets and axis-parallel rectangular ranges. The same bound holds for points in the plane and "fat" triangular ranges and for point sets in R-3 and axis-parallel boxes; these are the first known nontrivial bounds for these range spaces. Our technique also yields improved bounds on the size of epsilon-nets in the more general context considered by Clarkson and Varadarajan. For example, we show the existence of epsilon-nets of size O (1/epsilon log log log 1/epsilon) for the dual range space of "fat" regions and planar point sets (where the regions are the ground objects and the ranges are subsets stabbed by points). Plugging our bounds into the technique of Bronnimann and Goodrich or of Even, Rawitz, and Shahar, we obtain improved approximation factors (computable in expected polynomial time by a randomized algorithm) for the HITTING SET or the SET COVER problems associated with the corresponding range spaces.
dc.language.iso en_US
dc.publisher Society for Industrial & Applied Mathematics (SIAM)
dc.relation.isversionof 10.1137/090762968
dc.subject geometric range spaces
dc.subject epsilon-nets
dc.subject exponential decay lemma
dc.subject set cover
dc.subject hitting set
dc.subject davenport-schinzel sequences
dc.subject approximation algorithms
dc.subject computational
dc.subject geometry
dc.subject improved bounds
dc.subject fat triangles
dc.subject vc-dimension
dc.subject union
dc.subject complexity
dc.subject objects
dc.subject computer science, theory & methods
dc.subject mathematics, applied
dc.title SMALL-SIZE epsilon-NETS FOR AXIS-PARALLEL RECTANGLES AND BOXES
dc.title.alternative
dc.type Other article
dc.description.version Version of Record
duke.date.pubdate 2010-00-00
duke.description.issue 7
duke.description.volume 39
dc.relation.journal Siam Journal on Computing
pubs.begin-page 3248
pubs.end-page 3282


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record