Show simple item record Ezra, Esther en_US 2011-06-21T17:27:53Z 2011-06-21T17:27:53Z 2010 en_US
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. en_US
dc.identifier.issn 0097-5397 en_US
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. en_US
dc.language.iso en_US en_US
dc.publisher SIAM PUBLICATIONS en_US
dc.relation.isversionof doi:10.1137/090762968 en_US
dc.subject geometric range spaces en_US
dc.subject epsilon-nets en_US
dc.subject exponential decay lemma en_US
dc.subject set cover en_US
dc.subject hitting set en_US
dc.subject davenport-schinzel sequences en_US
dc.subject approximation algorithms en_US
dc.subject computational en_US
dc.subject geometry en_US
dc.subject improved bounds en_US
dc.subject fat triangles en_US
dc.subject vc-dimension en_US
dc.subject union en_US
dc.subject complexity en_US
dc.subject objects en_US
dc.subject computer science, theory & methods en_US
dc.subject mathematics, applied en_US
dc.title.alternative en_US
dc.description.version Version of Record en_US 2010-00-00 en_US
duke.description.endpage 3282 en_US
duke.description.issue 7 en_US
duke.description.startpage 3248 en_US
duke.description.volume 39 en_US
dc.relation.journal Siam Journal on Computing en_US

Files in this item

This item appears in the following Collection(s)

Show simple item record