Computational complexity for the problem of optimal intersections of straight line segments by disks

Computational complexity and exact polynomial algorithms are reported for the problem of stabbing a set of straight line segments with a least cardinality set of disks of fixed radii $r>0$, where the set of segments forms a straight line drawing $G=(V,E)$ of a planar graph without edge crossings. Similar geometric problems arise in network security applications (Agarwal et al., 2013). We establish the strong NP-hardness of the problem for edge sets of Delaunay triangulations, Gabriel graphs, and other subgraphs (which are often used in network design) for $r\in [d_{\min},\eta d_{\max}]$ and some constant $\eta$, where $d_{\max}$ and $d_{\min}$ are the Euclidean lengths of the longest and shortest graph edges, respectively.