On pseudo-disk hypergraphs
Boris Aronov, Anirudh Donakonda, Esther Ezra, Rom Pinchasi
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.
Computational Geometry: Theory and Applications
https://doi.org/10.1016/j.comgeo.2020.101687
Approximation algorithms
Hypergraphs of finite VC dimension
Minimum-weight dominating set
Planar graphs
Pseudo-disks
Computational Theory and Mathematics
10.1016/j.comgeo.2020.101687
Dive into the research topics of 'On pseudo-disk hypergraphs'. Together they form a unique fingerprint.
Hypergraph Mathematics 100%
Polynomials Engineering & Materials Science 79%
Subset Mathematics 28%
Dominating Set Mathematics 26%
Cardinality Mathematics 20%
Polynomial time Mathematics 20%
Upper bound Mathematics 16%
Generalise Mathematics 14%
Aronov, B., Donakonda, A., Ezra, E., & Pinchasi, R. (2021). On pseudo-disk hypergraphs. Computational Geometry: Theory and Applications, 92, [101687]. https://doi.org/10.1016/j.comgeo.2020.101687
On pseudo-disk hypergraphs. / Aronov, Boris; Donakonda, Anirudh; Ezra, Esther; Pinchasi, Rom.
In: Computational Geometry: Theory and Applications, Vol. 92, 101687, 01.2021.
Aronov, B, Donakonda, A, Ezra, E & Pinchasi, R 2021, 'On pseudo-disk hypergraphs', Computational Geometry: Theory and Applications, vol. 92, 101687. https://doi.org/10.1016/j.comgeo.2020.101687
Aronov B, Donakonda A, Ezra E, Pinchasi R. On pseudo-disk hypergraphs. Computational Geometry: Theory and Applications. 2021 Jan;92. 101687. https://doi.org/10.1016/j.comgeo.2020.101687
Aronov, Boris ; Donakonda, Anirudh ; Ezra, Esther ; Pinchasi, Rom. / On pseudo-disk hypergraphs. In: Computational Geometry: Theory and Applications. 2021 ; Vol. 92.
@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 = "Funding Information: Work on this paper by Boris Aronov has been supported by NSA MSP Grant H98230-10-1-0210, by NSF Grants CCF-08-30691, CCF-11-17336, CCF-12-18791, and CCF-15-40656, and by U.S.-Israel Binational Science Foundation grant 2014/170.Work on this paper by Anirudh Donakonda has been partially supported by NSF Grant CCF-11-17336.Work on this paper by Esther Ezra has been supported by ISF Grant 824/17, NSF under grants CAREER CCF-15-53354, CCF-11-17336, and CCF-12-16689.Work on this paper by Rom Pinchasi has been supported by ISF grant No. 409/16. Publisher Copyright: {\textcopyright} 2020 Elsevier B.V.",
doi = "10.1016/j.comgeo.2020.101687",
journal = "Computational Geometry: Theory and Applications",
T1 - On pseudo-disk hypergraphs
AU - Aronov, Boris
AU - Donakonda, Anirudh
AU - Ezra, Esther
AU - Pinchasi, Rom
N1 - Funding Information: Work on this paper by Boris Aronov has been supported by NSA MSP Grant H98230-10-1-0210, by NSF Grants CCF-08-30691, CCF-11-17336, CCF-12-18791, and CCF-15-40656, and by U.S.-Israel Binational Science Foundation grant 2014/170.Work on this paper by Anirudh Donakonda has been partially supported by NSF Grant CCF-11-17336.Work on this paper by Esther Ezra has been supported by ISF Grant 824/17, NSF under grants CAREER CCF-15-53354, CCF-11-17336, and CCF-12-16689.Work on this paper by Rom Pinchasi has been supported by ISF grant No. 409/16. Publisher Copyright: © 2020 Elsevier B.V.
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
U2 - 10.1016/j.comgeo.2020.101687
DO - 10.1016/j.comgeo.2020.101687
JO - Computational Geometry: Theory and Applications
JF - Computational Geometry: Theory and Applications