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

Loading...
Thumbnail Image

Date

2010

Journal Title

Journal ISSN

Volume Title

Repository Usage Stats

306
views
464
downloads

Citation Stats

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.

Department

Description

Provenance

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.

Published Version (Please cite this version)

10.1137/090762968


Unless otherwise indicated, scholarly articles published by Duke faculty members are made available here with a CC-BY-NC (Creative Commons Attribution Non-Commercial) license, as enabled by the Duke Open Access Policy. If you wish to use the materials in ways not already permitted under CC-BY-NC, please consult the copyright owner. Other materials are made available here through the author’s grant of a non-exclusive license to make their work openly accessible.