Computational Complexity for the Problem of Optimal Intersection of Straight Line Segments by Disks

Abstract

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 plane 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 ∈ [d_min, ηd_max] and some constant η, where d_max and d_min are the Euclidean lengths of the longest and shortest graph edges, respectively.