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 ( 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 minimum-weight dominating set in a collection of pseudo-disks in the plane, in expected polynomial time.