Small-size epsilon-nets for axis-parallel rectangles and boxes

We show the existence of ε-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 reals 3 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 ε-nets of size

Authors

• Boris Aronov
• Esther Ezra
• Micha Sharir

Keywords

• ε-nets
• geometric range spaces
• hitting set
• randomized algorithms
• set cover