On pseudo-disk hypergraphs

Boris Aronov, Anirudh Donakonda, Esther Ezra, Rom Pinchasi

    Research output: Contribution to journalArticlepeer-review

    Abstract

    Let F be a family of pseudo-disks in the plane, and P be a finite subset of F. Consider the hyper-graph H(P,F) whose vertices are the pseudo-disks in P and the edges are all subsets of P of the form {D∈P|D∩S≠∅}, where S is a pseudo-disk in F. We give an upper bound of O(nk3) for the number of edges in H(P,F) of cardinality at most k. This generalizes a result of Buzaglo et al. [4]. As an application of our bound, we obtain an algorithm that computes a constant-factor approximation to the minimum-weight dominating set in a collection of pseudo-disks in the plane, in expected polynomial time.

    Original languageEnglish (US)
    Article number101687
    JournalComputational Geometry: Theory and Applications
    Volume92
    DOIs
    StatePublished - Jan 2021

    Keywords

    • Approximation algorithms
    • Hypergraphs of finite VC dimension
    • Minimum-weight dominating set
    • Planar graphs
    • Pseudo-disks

    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 'On pseudo-disk hypergraphs'. Together they form a unique fingerprint.

    Cite this