Small weak epsilon-nets

Boris Aronov, Franz Aurenhammer, Ferran Hurtado, Stefan Langerman, David Rappaport, Carlos Seara, Shakhar Smorodinsky

    Research output: Contribution to journalArticlepeer-review

    Abstract

    Given a set P of points in the plane, a set of points Q is a weak -net with respect to a family of sets S (e.g., rectangles, disks, or convex sets) if every set of S containing |P| points contains a point of Q. In this paper, we determine bounds on iS, the smallest epsilon that can be guaranteed for any P when |Q|=i, for small values of i.

    Original languageEnglish (US)
    Pages (from-to)455-462
    Number of pages8
    JournalComputational Geometry: Theory and Applications
    Volume42
    Issue number5
    DOIs
    StatePublished - Jul 2009

    Keywords

    • Convex sets
    • Rectangles
    • Set systems
    • Weak epsilon-nets

    ASJC Scopus subject areas

    • Computer Science Applications
    • Geometry and Topology
    • Control and Optimization
    • Computational Theory and Mathematics
    • Computational Mathematics

    Fingerprint Dive into the research topics of 'Small weak epsilon-nets'. Together they form a unique fingerprint.

    Cite this