On pseudo-disk hypergraphs

DOI10.1016/J.COMGEO.2020.101687MaRDI QIDQ827317zbMATH OpenOpenAlexFDO

Authors Boris Aronov, Anirudh Donakonda, Esther Ezra, Rom Pinchasi

Publication date 7 January 2021

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1802.08799

zbMATH Keywords

approximation algorithmsplanar graphspseudo-diskshypergraphs of finite VC-dimensionminimum-weight dominating set

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Planar graphs; geometric and topological aspects of graph theory (05C10) Hypergraphs (05C65)

Abstract: Let $F$ be a family of pseudo-disks in the plane, and $P$ be a finite subset of $F$. Consider the hypergraph $H(P,F)$ whose vertices are the pseudo-disks in $P$ and the edges are all subsets of $P$ of the form $DinPmidDcapSeqemptyset$, where $S$ is a pseudo-disk in $F$. We give an upper bound of $O(n{k}^3)$ for the number of edges in $H(P,F)$ of cardinality at most $k$. This generalizes a result of Buzaglo et al. (2013). As an application of our bound, we obtain an algorithm that computes a constant-factor approximation to the smallest _weighted_ dominating set in a collection of pseudo-disks in the plane, in expected polynomial time.

Recommendations

• Approximation algorithms for maximum independent set of pseudo-disks
• Approximation algorithms for maximum independent set of pseudo-disks
• Algorithms for dominating set in disk graphs: breaking the \(\log n\) barrier (extended abstract)
• Coloring intersection hypergraphs of pseudo-disks
• Coloring intersection hypergraphs of pseudo-disks

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1424290 (Why is no real title available?)
• A (4 + ε)-Approximation for the Minimum-Weight Dominating Set Problem in Unit Disk Graphs
• A Greedy Heuristic for the Set-Covering Problem
• Algorithms for dominating set in disk graphs: breaking the \(\log n\) barrier (extended abstract)
• Applications of random sampling in computational geometry. II
• Approximation and Online Algorithms
• Coloring intersection hypergraphs of pseudo-disks
• Density of range capturing hypergraphs
• Domination in Geometric Intersection Graphs
• Dynamic connectivity for axis-parallel rectangles
• Improved results on geometric hitting set problems
• NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
• On the ratio of optimal integral and fractional covers
• On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles
• Packing and covering with non-piercing regions
• Reducibility among combinatorial problems
• Removing even crossings
• Topological hypergraphs
• Toward a theory of crossing numbers
• Unit disk graphs
• Weighted capacitated, priority, and geometric set cover via improved quasi-uniform sampling

Cited in

(8)

• A finite family of pseudodiscs must include a ``small pseudodisc
• On tangencies among planar curves with an application to coloring L-shapes
• Coloring intersection hypergraphs of pseudo-disks
• On tangencies among planar curves with an application to coloring L-shapes
• Conflict-free colouring of subsets
• On the number of hyperedges in the hypergraph of lines and pseudo-discs
• The \(\varepsilon\)-\(t\)-net problem
• Guarding polyominoes under \(k\)-hop visibility

This page was built for publication: On pseudo-disk hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q827317)