TY - GEN
T1 - Small-size ε-nets for axis-parallel rectangles and boxes
AU - Aronov, Boris
AU - Ezra, Esther
AU - Sharir, Micha
PY - 2009
Y1 - 2009
N2 - We show the existence of e-nets of size O (1/ε log log 1/ε) for planar point sets and axis-parallel rectangular ranges. The same bound holds for points in the plane with "fat" triangular ranges, and for point sets in R3 and axis-parallel boxes; these are the first known non-trivial bounds for these range spaces. Our technique also yields improved bounds on the size of ε-nets in the more general context considered by Clarkson and Varadarajan. For example, we show the existence of e-nets of size O (1/εe log log log 1/ε) 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 Brönnimann and Goodrich, we obtain improved approximation factors (computable in randomized polynomial time) for the hitting set or the set cover problems associated with the corresponding range spaces.
AB - We show the existence of e-nets of size O (1/ε log log 1/ε) for planar point sets and axis-parallel rectangular ranges. The same bound holds for points in the plane with "fat" triangular ranges, and for point sets in R3 and axis-parallel boxes; these are the first known non-trivial bounds for these range spaces. Our technique also yields improved bounds on the size of ε-nets in the more general context considered by Clarkson and Varadarajan. For example, we show the existence of e-nets of size O (1/εe log log log 1/ε) 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 Brönnimann and Goodrich, we obtain improved approximation factors (computable in randomized polynomial time) for the hitting set or the set cover problems associated with the corresponding range spaces.
KW - E-nets
KW - Geometric range spaces
KW - Hitting set
KW - Randomized algorithms
KW - Set cover
UR - http://www.scopus.com/inward/record.url?scp=70350668803&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=70350668803&partnerID=8YFLogxK
U2 - 10.1145/1536414.1536501
DO - 10.1145/1536414.1536501
M3 - Conference contribution
AN - SCOPUS:70350668803
SN - 9781605585062
T3 - Proceedings of the Annual ACM Symposium on Theory of Computing
SP - 639
EP - 648
BT - STOC'09 - Proceedings of the 2009 ACM International Symposium on Theory of Computing
T2 - 41st Annual ACM Symposium on Theory of Computing, STOC '09
Y2 - 31 May 2009 through 2 June 2009
ER -