On Pseudo-disk Hypergraphs

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 ${D \in P \mid D \cap S \neq \emptyset}$,where$S$isapseudo-diskin$F$\mathrm{.}Wegiveanupperboundof$O(nk^3)$forthenumberofedgesin$H(P,F)$ofcardinalityatmost$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.