Computational complexity and approximability are studied for a problem of intersecting a set of straight line segments with the smallest 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 problems arise e.g. in network security applications (Agarwal et al., 2013). We claim strong NP-hardness of the problem within classes of (edge sets of) Delaunay triangulations, Gabriel graphs and other subgraphs (which are often used in network design) for r 2 [dmin; dmax] and some constant where dmax and dmin are Euclidean lengths of the longest and shortest graph edges respectively. Fast O(jEj log jEj)-time O(1)-approximation algorithm is proposed within the class of straight line drawings of planar graphs for which the inequality r dmax holds uniformly for some constant > 0: Many problems in computational geometry can be posed in the form of the geometric Hitting Set problem including well known disk covering problems [7] which arise in facility location and Art Gallery problems [13] from security and monitoring applications. In the classical geometric Hitting Set problem one seeks a small cardinality set of “representatives” for a given set of geometric objects in the following sense: Hitting Set: given a family N of subsets (objects) of Rd and a set U Rd; find the smallest cardinality set H U such that N \ H 6= ; for every N 2 N : Refining its complexity status and designing exact and approximation algorithms for different types of geometric objects is still an area of active research, see e.g. [4], [8] and [11]. In this paper we deal with a geometric problem which can be considered as a particular type of the Hitting Set problem on the plane: Intersecting Plane Graph with Disks (IPGD): given a straight line drawing of an arbitrary simple1 planar graph G = (V; E) without edge crossings and a constant r > 0; find the smallest cardinality set C R2 of points (disk centers) such that each edge e 2 E is within Euclidean distance r from some point c = c(e) 2 C or, equivalently, the disk of radius r centered at c intersects e: IPGD coincides with Hitting Set if we set N := Nr(E) = fNr(e)ge2E and U := R2 where Nr(e) = Br(0) + e = fx + y : x 2 Br(0); y 2 eg is Euclidean r-neighbourhood of e (having form of Minkowski sum) and Copyright c by the paper's authors. Copying permitted for private and academic purposes. In: A.A. Makhnev, S.F. Pravdin (eds.): Proceedings of the International Youth School-conference ¾SoProMat-2017¿, Yekaterinburg, Russia, 06-Feb-2017, published at http://ceur-ws.org 1a graph without loops and parallel edges
Br(x) is the disk of radius r centered at x 2 R2: Of course, IPGD coincides with well known Continuous Disk
Cover problem (denoted by CDC in the sequel) [
In this paper computational complexity and approximability of IPGD are studied for simple plane graphs
with either r 2 [dmin; dmax] or r = (dmax) where dmax and dmin are lengths of the longest and shortest edges of
G: Our emphasis is on those classes of simple plane graphs that are defined by some distance function, namely,
on Delaunay triangulations and some of their connected subgraphs (e.g. for Gabriel graphs). These graphs are
often called proximity graphs. Delaunay triangulations (being geometric spanners) are plane graphs which admit
efficient geometric routing algorithms [
Related work. Most of related results are about computational complexity and approximability of close settings
of the Hitting Set problem. An aspect ratio of a closed convex set N with int N 6= ?2 coincides with the ratio
of the minimum radius of the disk which contains N to the maximum radius of the disk which is contained in
N: For example, each object Nr(e) has aspect ratio equal to 1 + d(e) where d(e) is the length of the edge e:
2r
APX-hardness of the discrete3 Hitting Set problem is presented for families of axis-parallel rectangles with
generally unbounded aspect ratio [
Results. Our results report complexity and approximation algorithms for the IPGD problem within several classes of plane graphs under different assumptions on r: Let S be a set of n points in general position on the plane no 4 of which are cocircular. We call a plane graph G = (S; E) a Delaunay triangulation when [u; v] 2 E iff there is a disk T such that u; v 2 bd T 4 and S \ int T = ?: Finally, a plane graph G = (S; E) is named as nearest neighbour graph when [u; v] 2 E iff either u or v is the nearest Euclidean neighbour for v or u respectively. Hardness results. Our first result claims strong NP-hardness of IPGD within the class of Delaunay triangulations and some known classes of their connected subgraphs (Gabriel, relative neighbourhood graphs) for r 2 [dmin; dmax] and = ddmmainx = O(n) where n = jSj: IPGD remains strongly NP-hard within the class of nearest neighbour graphs for r 2 [dmax; dmax] with large constant and 4: Furthermore, we have the same hardness results under the same restrictions on r and even if we are bound to choose points of C close to vertices of G:
The upper bound on for Delaunay triangulations is comparable with the lower bound = p3n2 which
holds true (with positive probability) for Delaunay triangulations produced by n random independent points on
the unit disk [
In distinction to known results for the Hitting Set problem mentioned above our study is mostly for its
continuous setting with the structured system Nr(E) formed by an edge set of a specific plane graph; each set
from Nr(E) is of the special form of Minkowski sum of some graph edge and the radius r disk. Our proofs are
elaborate complexity reductions from the CDC problem which is intimately related to IPGD.
Approximation algorithm. Our hardness proofs are likely to give W [
We give complexity analysis for the IPGD problem by first considering its setting where r 2 [dmin; dmax]: Under this restriction on r IPGD coincides neither with known Vertex Cover problem nor with CDC. In fact it is equivalent (see the Introduction) to the geometric Hitting Set problem for the set Nr(E) of Euclidean r-neighbourhoods of edges of G: For the IPGD problem we claim its strong NP-hardness even if we restrict the graph G to be either a Delaunay triangulation or some of its known subgraphs. We keep the ratio = ddmmainx bounded from above, thus, imposing an upper bound on the ratio of the largest and the smallest aspect ratio of objects from Nr(E): We also show that IPGD remains intractable even in its simple case where r = (dmax) and is bounded by some small constant or, equivalently, when objects of Nr(E) have close constant aspect ratio.
Our first hardness result for IPGD is obtained by using a complexity reduction from the CDC problem. Below we describe a class of hard instances of the CDC problem which correspond to hard instances of the IPGD problem for Delaunay triangulations with relatively small upper bound on the parameter : Hardness result for the CDC problem. To single out the class of hard instances of the CDC problem we use a reduction from the strongly NP-complete minimum dominating set problem which is formulated as follows: given a simple planar graph G0 = (V0; E0) of degree at most 3; find the smallest cardinality set V00 V0 such that for each u 2 V0nV00 there is some v = v(u) 2 V00 which is adjacent to u:
Below an integer grid denotes the set of points on the plane with integer-valued coordinates within some
bounded interval. An orthogonal drawing of the graph G0 on some integer grid is the drawing whose vertices are
represented by points on that grid whereas its edges are given in the form of polylines formed by sequences of
connected axis-parallel straight line segments of the form [p1; p2]; [p2; p3]; : : : ; [pk 1; pk] intersecting only at the
edge endpoints, where each point pi again belongs to the grid. In [
Lemma 1. Let X Z2; r 1 be some integer and (u; v; w) be the minimum of two Euclidean distances from u 2 X to circles of radius r passing through distinct points v and w from X with jv wj2 2r; where Z is the set of integers and j j2 is Euclidean norm. Then
min u2=C(v;w);v6=w;u;v;w2X;jv wj2 2r (u; v; w) where C(v; w) is the union of two radius r circles through v and w:
The complexity of the following restricted form of IPGD is also studied.
Vertex Restricted IPGD (VRIPGD( )): given a simple plane graph G = (V; E); a constant > 0 and a constant r > 0; find the least cardinality set C R2 such that each e 2 E is within (Euclidean) distance r from some point c = c(e) 2 C and C S B (v): v2V Theorem 2. Both IPGD and VRIPGD( ) problems are strongly NP-hard for r 2 [dmin; dmax]; = O(n) and = (r) within the class of Delaunay triangulations, where n is the number of vertices in triangulation. Proof. Let us prove that IPGD is strongly NP-hard. Proof technique for the VRIPGD( ) problem is analogous. For any hard instance of the CDC problem given in theorem 1 we build the IPGD problem instance with r = r0 + as follows where = 2000122r011 : For every u 2 D points u0 and v0 are found such that ju u0j1 =2 and ju v0j1 =2 where Iu = [u0; v0] has Euclidean length at least =2: More specifically, let us set ID = fIu = [u0; v0] : u 2 Dg: Endpoints of segments from ID are constructed in sequential manner in polynomial time and space by defining a new segment Iu to provide generality position for the set of endpoints of the set ID0 [ fIug; D0 D; where segments of ID0 are already defined. Here endpoints of Iu are chosen in the rational grid that contains u whose elementary square size is jDc1j2 jDc1j2 for some small absolute rational constant c1: Assuming u = (ux; uy); the point u0 is chosen in the lower part of the grid with y-coordinates less than uy =4 whereas v0 is taken from the upper one for which y-coordinates exceed uy + =4:
Let S be the set of endpoints of segments from ID: Every disk having Iu as its diameter does not contain
any points of S distinct from endpoints of Iu: Let G = (S; E) be a Delaunay triangulation for S which can be
computed in polynomial time and space in jDj: Obviously, each segment Iu coincides with some edge from E:
We have dmin r and = O(jSj): It remains to prove that r dmax: Due to remark 1 and the construction
of the set D (see fig. 1 [
Let k be a positive integer. Obviously, centers of at most k disks of radius r0 containing D in their union give centers of radius r > r0 disks whose union is intersected with each segment from E: Conversely, let T be a disk of radius r which intersects a subset ID0 = fIu : u 2 D0g of segments for some D0 D: When jD0j = 1; it is easy to transform T to a disk which contains the segment ID0 : Points of D have integer coordinates. Moreover, squared (Euclidean) distance between each pair of points of the subset D0 does not exceed (2r0 +4 )2 = 4r02 +16r0 +16 2: Therefore points from D0 are located within the distance 2r0 from each other. Let us use Helly theorem. Let R be the minimum radius of the disk T0 containing any triple u1; u2 and u3 from D0: W.l.o.g. we suppose that, say, u1 and u2 are on the boundary of T0 and denote its center by O: Obviously, R r0 + 2 : Let us show that the case R > r0 is void. We slightly shift the center of T0 (along the midperpendicular to [u1; u2]) to have u1 and u2 at the distance r0 from the shifted center O0: The distance from the point u3 to the radius r0 circle centered at O0 does not exceed where 1 = ju1 2u2j2 r0: By lemma 1 we have R r0: Thus, D0 is contained in some disk of radius r0: Given a set of points, the smallest radius disk can be found in polynomial time and space which covers this set. Therefore we can convert any set of at most k disks of radius r whose union is intersected with each segment from E to some set of at most k disks of radius r0 whose union covers D: Proof is completed.
Using corollary 1 of section 4.2 from [
The IPGD problem hardness for other classes of proximity graphs. The same proof technique could be applied for proving the problem hardness within the other classes of proximity graphs. Let us start with some definitions. The following graphs are connected subgraphs of Delaunay triangulations. A plane graph G = (S; E) is called a Gabriel graph where [u; v] 2 E iff the disk having [u; v] as its diameter does not contain any other points of S distinct from u and v: A relative neighbourhood graph is the plane graph G with the same vertex set for which [u; v] 2 E iff there is no any other point w 2 S such that w 6= u; v with maxfju wj2; jv wj2g < ju vj2: Finally, a plane graph is called a minimum Euclidean spanning tree if it is the minimum weight spanning tree of the weighted complete graph KjSj whose vertices are points of S such that its edge weight is given by the Euclidean distance between the edge endpoints. q 12 = 1 480r05 ; jO u3j2 + jO
O0j2 r0 2 + (r0 + 2 )2 Below the approximation algorithm is reported for the IPGD problem whose approximation factor depends on the maximum aspect ratio among objects of Nr(E): More specifically, let us focus on the case of IPGD where the inequality r dm2ax holds uniformly within some class G of simple plane graphs for a constant > 0: It corresponds to the situation where objects from the system Nr(E) have their aspect ratio bounded from above by 1 + : In this case it turns out that the problem admits an O(1)-approximation algorithm whose factor depends on : The following auxiliary problem is considered to formulate it.
Cover endpoints of segments with disks (CESD). Let S(G) V be the set of endpoints of edges of G:
It is required to find the smallest cardinality set of radius r disks whose union contains S(G):
Algorithm. Compute and output 8-approximate solution to the CESD problem using
O(jEj log OP TCESD(S(G); r))-time algorithm (see sections 2 and 4 from [
We call a subset V 0 V by a vertex cover for G = (V; E) when e \ V 0 6= ? for any e 2 E: The statement below bounds the ratio of optima for CESD and IPGD problems in the general case where S(G) is an arbitrary vertex cover of the graph G: Statement 1. The following bound holds true for any graph G 2 G without isolated vertices: OP TCESD(S(G); r)
OP TIP GD(G; r) p(1 + 2 ) where p(x) is the smallest number of unit disks needed to cover radius x disk.
Proof. Let C0 = C0(G; r) R2 be an optimal solution to IPGD for a given G 2 G : Set E(c; G) := fe 2 E : c 2 Nr(e)g; c 2 C0: For every e 2 E(c; G) there is a point c(e) 2 e with jc c(e)j2 r: Any point from the set S(c; G) of endpoints of segments from E(c; G) is within the distance r + dmax from the point c: Due to definition of p; at most p(1 + 2 ) radius r disks are needed to cover radius r + dmax disk. Therefore the set S(G) S S(c; G) c2C0 is contained in the union of at most jC0jp(1 + 2 ) radius r disks.
Corollary 2. The Algorithm is 8p(1 + 2 )-approximate.
Remark 2. Approximation factor of the Algorithm is in fact lower when G is the subclass of Delaunay triangulations or their subgraphs. Indeed, in this case there is no need to cover the whole radius r + dmax disk with radius r disks.
Remark 3. If S(G) is the set of midpoints of segments from E; the Algorithm is 8p(1 + )-approximate.
A similar but more complex O(jEj1+")-time constant factor approximation algorithm is given in [
Complexity and approximability are studied for the problem of intersecting a structured set of straight line segments with the smallest number of disks of radii r > 0 where a structural information about segments is given in the form of an edge set of a proximity graph. It is shown that the problem is strongly NP-hard within the class of Delaunay triangulations and some of their subgraphs for r within the range of lengths of segments. Fast O(1)-approximation algorithm is given for sufficiently large values of r:
Our work was supported by the Russian Science Foundation, project № 14-11-00109.