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

Boris Aronov, Esther Ezra, Micha Sharir

    Research output: Contribution to journalArticlepeer-review


    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 and "fat" triangular ranges and for point sets in R3 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 ε-nets in the more general context considered by Clarkson and Varadarajan. For example, we show the existence of ε-nets of size O (1/ε 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 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.

    Original languageEnglish (US)
    Pages (from-to)3248-3282
    Number of pages35
    JournalSIAM Journal on Computing
    Issue number7
    StatePublished - 2010


    • Exponential decay lemma
    • Geometric range spaces
    • ε-nets

    ASJC Scopus subject areas

    • General Computer Science
    • General Mathematics


    Dive into the research topics of 'Small-size ε-nets for axis-parallel rectangles and boxes'. Together they form a unique fingerprint.

    Cite this