On pseudo-disk hypergraphs

Boris Aronov; Anirudh Donakonda; Esther Ezra; Rom Pinchasi

doi:10.1016/j.comgeo.2020.101687

On pseudo-disk hypergraphs

Boris Aronov, Anirudh Donakonda, Esther Ezra, Rom Pinchasi

Research output: Contribution to journal › Article › peer-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(nk³) 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 language	English (US)
Article number	101687
Journal	Computational Geometry: Theory and Applications
Volume	92
DOIs	https://doi.org/10.1016/j.comgeo.2020.101687
State	Published - 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

Access to Document

10.1016/j.comgeo.2020.101687

Cite this

@article{3acd453d5bfd4990b58e93a228669aad,

title = "On pseudo-disk hypergraphs",

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.",

keywords = "Approximation algorithms, Hypergraphs of finite VC dimension, Minimum-weight dominating set, Planar graphs, Pseudo-disks",

author = "Boris Aronov and Anirudh Donakonda and Esther Ezra and Rom Pinchasi",

note = "Publisher Copyright: {\textcopyright} 2020 Elsevier B.V.",

year = "2021",

month = jan,

doi = "10.1016/j.comgeo.2020.101687",

language = "English (US)",

volume = "92",

journal = "Computational Geometry: Theory and Applications",

issn = "0925-7721",

publisher = "Elsevier",

}

TY - JOUR

T1 - On pseudo-disk hypergraphs

AU - Aronov, Boris

AU - Donakonda, Anirudh

AU - Ezra, Esther

AU - Pinchasi, Rom

PY - 2021/1

Y1 - 2021/1

N2 - 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.

AB - 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.

KW - Approximation algorithms

KW - Hypergraphs of finite VC dimension

KW - Minimum-weight dominating set

KW - Planar graphs

KW - Pseudo-disks

UR - http://www.scopus.com/inward/record.url?scp=85087812707&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85087812707&partnerID=8YFLogxK

U2 - 10.1016/j.comgeo.2020.101687

DO - 10.1016/j.comgeo.2020.101687

M3 - Article

AN - SCOPUS:85087812707

SN - 0925-7721

VL - 92

JO - Computational Geometry: Theory and Applications

JF - Computational Geometry: Theory and Applications

M1 - 101687

ER -

On pseudo-disk hypergraphs

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this