Introduction

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 R d and a set U ⊆ R d , find the smallest cardinality set H ⊆ U such that N ∩ H = ∅ for every N ∈ 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 simple 1 planar graph G = (V, E) without edge crossings and a constant r > 0, find the smallest cardinality set C ⊂ R 2 of points (disk centers) such that each edge e ∈ E is within Euclidean distance r from some point c = c(e) ∈ C or, equivalently, the disk of radius r centered at c intersects e.

IPGD coincides with Hitting Set if we set N := N r (E) = {N r (e)} e∈E and U := R2 where N r (e) = B r (0) + e = {x + y : x ∈ B r (0), y ∈ e} is Euclidean r-neighbourhood of e (having form of Minkowski sum) and B r (x) is the disk of radius r centered at x ∈ R 2 . Of course, IPGD coincides with well known Continuous Disk Cover problem (denoted by CDC in the sequel) [7] in the case where segments of E have zero lengths. Finally, we get classical Vertex Cover problem for planar graphs when r = 0.

In this paper computational complexity and approximability of IPGD are studied for simple plane graphs with either r ∈ [d min , d max ] or r = Ω(d max ) where d max and d min 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 [2], thus, representing convenient network topologies. Gabriel graphs arise in modeling wireless networks [3]. 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 = ∅ 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 N r (e) has aspect ratio equal to 1 + d (e) 2r where d(e) is the length of the edge e. APX-hardness of the discrete 3 Hitting Set problem is presented for families of axis-parallel rectangles with generally unbounded aspect ratio [4] and for families of triangles of bounded aspect ratio [8]. Strong NP-hardness is also well known for the CDC problem [10]. 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] ∈ E iff there is a disk T such that u, v ∈ bd T4 and S ∩ int T = ∅. Finally, a plane graph G = (S, E) is named as nearest neighbour graph when [u, v] ∈ 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 ∈ [d min , d max ] and µ = dmax dmin = O(n) where n = |S|. IPGD remains strongly NP-hard within the class of nearest neighbour graphs for r ∈ [d max , ηd max ] 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 µ = Ω 3 √ n 2 which holds true (with positive probability) for Delaunay triangulations produced by n random independent points on the unit disk [1]. Thus, declared restrictions on r and µ define natural instances of IPGD. An upper bound on µ implies an upper bound on the ratio of the largest and the smallest aspect ratio of objects from N r (E). The Hitting Set problem is generally easier when sets from N have almost equal aspect ratio bounded from above by some constant. Our result for the class of nearest neighbour graphs gives the problem hardness in the case where objects of N r (E) have almost equal constant aspect ratio.

In distinction to known results for the Hitting Set problem mentioned above our study is mostly for its continuous setting with the structured system N r (E) formed by an edge set of a specific plane graph; each set from N r (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 [1]-hardness of IPGD taking into account results from [9]. Therefore, constant factor approximation algorithms are of particular interest. A polynomial time algorithm (which is denoted by A) for IPGD is said to be f -approximate (or to have approximation factor f ) iff the following bound holds true for any plane graph G from some class of plane graphs:

|C A (G, r)| OP T IP GD (G, r) ≤ f,

where C A (G, r) is a feasible solution to IPGD output by A for a given plane graph G and radius r whereas OP T IP GD (G, r) denotes the problem optimum. In this work we present an 8p(1 + 2λ)-approximation O(|E| log |E|)-time algorithm for IPGD when the inequality r ≥ dmax 2λ holds true uniformly within some class of simple plane graphs for a constant λ > 0, where p(x) is the smallest number of unit disks needed to cover any disk of radius x > 1. It corresponds to the case where segments from E have their lengths bounded from above by some linear function of r, or, in other words, when objects from N r (E) have their aspect ratio bounded from above by 1 + λ.

Hardness results

We give complexity analysis for the IPGD problem by first considering its setting where r ∈ [d min , d max ]. 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 N r (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 µ = dmax dmin bounded from above, thus, imposing an upper bound on the ratio of the largest and the smallest aspect ratio of objects from N r (E). We also show that IPGD remains intractable even in its simple case where r = Θ(d max ) and µ is bounded by some small constant or, equivalently, when objects of N r (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 G 0 = (V 0 , E 0 ) of degree at most 3, find the smallest cardinality set

V 0 ⊆ V 0 such that for each u ∈ V 0 \V 0 there is some v = v(u) ∈ V 0 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 G 0 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 [p 1 , p 2 ], [p 2 , p 3 ], . . . , [p k−1 , p k ] intersecting only at the edge endpoints, where each point p i again belongs to the grid. In [10] strong NP-hardness of CDC is proved by reduction from the minimum dominating set problem. This reduction involves using plane orthogonal drawing of G 0 on some integer grid. More specifically, a set D is build on that grid with V 0 ⊂ D. The resulting hard instance of the CDC problem is for the set D and some integer (constant) radius r 0 ≥ 1. Let us observe that G 0 admits an orthogonal drawing (theorem 1 [14]) on the grid of size

O(|V 0 |) × O(|V 0 |) whereas total length of each edge is O(|V 0 |).

Proof of the strong NP-hardness of CDC could be conducted taking into account this observation. We can formulate (see combination of theorems 1 and 3 [10]) Theorem 1. (Masuyama et. al., 1981 [10]) The CDC problem is strongly NP-hard for a constant integer radius r 0 and point sets D on the integer grid of size O(|D|) × O(|D|). It remains strongly NP-hard even if we restrict centers of radius r 0 disks to be at the points of D. Remark 1. For every simple planar graph G 0 of degree at most 3 its orthogonal drawing can be constructed such that at least one its edges is a polyline which is composed of at least two axis-parallel segments.

The IPGD problem hardness for Delaunay triangulations. To build a reduction from the CDC problem for the set D (as constructed in the proof of theorem 1) we exploit a simple idea that a radius r disk covers a set of points D ⊂ D iff a slightly larger disk intersects straight line segments, each of which is close to some point of D and has a small length with respect to distances between points of D. Then a proximity graph H is build whose vertex set coincides with the set of endpoints of small segments corresponding to points of D. Since H usually contains these small segments as its edges, this technique gives hardness for the IPGD problem within numerous classes of proximity graphs. The following technical lemma holds. Lemma 1. Let X ⊂ Z 2 , r ≥ 1 be some integer and ρ(u; v, w) be the minimum of two Euclidean distances from u ∈ X to circles of radius r passing through distinct points v and w from X with |v − w| 2 ≤ 2r, where Z is the set of integers and | • | 2 is Euclidean norm. Then 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 ⊂ R 2 such that each e ∈ E is within (Euclidean) distance r from some point c = c(e) ∈ C and C ⊂ v∈V B δ (v). |D| 2 × c1 |D| 2 for some small absolute rational constant c 1 . Assuming u = (u x , u y ), the point u 0 is chosen in the lower part of the grid with y-coordinates less than u y − δ/4 whereas v 0 is taken from the upper one for which y-coordinates exceed u y + δ/4.

Let S be the set of endpoints of segments from I D . Every disk having I u as its diameter does not contain any points of S distinct from endpoints of I u . Let G = (S, E) be a Delaunay triangulation for S which can be computed in polynomial time and space in |D|. Obviously, each segment I u coincides with some edge from E. We have d min ≤ r and µ = O(|S|). It remains to prove that r ≤ d max . Due to remark 1 and the construction of the set D (see fig. 1 [10]) the set S can be constructed such that the inequality r ≤ d max holds true for G. Moreover, representation length for vertices of S is polynomial with respect to representation length for points of D.

Let k be a positive integer. Obviously, centers of at most k disks of radius r 0 containing D in their union give centers of radius r > r 0 disks whose union is intersected with each segment from E. Conversely, let T be a disk of radius r which intersects a subset I D = {I u : u ∈ D } of segments for some D ⊆ D. When |D | = 1, it is easy to transform T to a disk which contains the segment I D . Points of D have integer coordinates. Moreover, squared (Euclidean) distance between each pair of points of the subset D does not exceed (2r 0 +4δ) 2 = 4r 2 0 +16r 0 δ +16δ 2 . Therefore points from D are located within the distance 2r 0 from each other. Let us use Helly theorem. Let R be the minimum radius of the disk T 0 containing any triple u 1 , u 2 and u 3 from D . W.l.o.g. we suppose that, say, u 1 and u 2 are on the boundary of T 0 and denote its center by O. Obviously, R ≤ r 0 + 2δ. Let us show that the case R > r 0 is void. We slightly shift the center of T 0 (along the midperpendicular to [u 1 , u 2 ]) to have u 1 and u 2 at the distance r 0 from the shifted center O . The distance from the point u 3 to the radius r 0 circle centered at O does not exceed

|O − u 3 | 2 + |O − O | 2 − r 0 ≤ 2δ + (r 0 + 2δ) 2 − δ 2 1 − r 2 0 − δ 2 1 = = 2δ + 4r 0 δ + 4δ 2 (r 0 + 2δ) 2 − δ 2 1 + r 2 0 − δ 2 1 ≤ 2δ + 2 r 0 δ + δ 2 < 1 480r 5 0 , where δ 1 = |u1−u2|2 2 ≤ r 0 .

By lemma 1 we have R ≤ r 0 . Thus, D is contained in some disk of radius r 0 . 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 r 0 whose union covers D. Proof is completed.

Using corollary 1 of section 4.2 from [1] and theorem 1 from [12] we arrive at the lower bound µ = Ω 3 √ n 2 which holds true with positive probability for Delaunay triangulations produced by n random uniform points on the unit disk. Thus, the order of the parameter µ for the considered class of hard instances of the IPGD problem is comparable with the one for random Delaunay triangulations.

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] ∈ 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] ∈ E iff there is no any other point w ∈ S such that w = u, v with max{|u − w| 2 , |v − w| 2 } < |u − v| 2 . Finally, a plane graph is called a minimum Euclidean spanning tree if it is the minimum weight spanning tree of the weighted complete graph K |S| whose vertices are points of S such that its edge weight is given by the Euclidean distance between the edge endpoints.

The proof of theorem 2 is extendable for classes of Gabriel, relative neighbourhood and nearest neighbour graphs. It is easy to observe that segments I u , u ∈ D, form a subset of edges of any minimum Euclidean spanning tree. Corollary 1. Both IPGD and VRIPGD(δ) problems are strongly NP-hard for r ∈ [d min , d max ], µ = O(n) and δ = Θ(r) within classes of Gabriel, relative neighbourhood graphs and minimum Euclidean spanning trees and for r ∈ [d max , ηd max ] and µ ≤ 4 within the class of nearest neighbour graphs where η is a large constant.

Let us note that IPGD becomes polynomially solvable for trees for r = 0 (see e.g. [5]).

Approximation algorithm for IPGD

Below the approximation algorithm is reported for the IPGD problem whose approximation factor depends on the maximum aspect ratio among objects of N r (E). More specifically, let us focus on the case of IPGD where the inequality r ≥ dmax 2λ holds uniformly within some class G λ of simple plane graphs for a constant λ > 0. It corresponds to the situation where objects from the system N r (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(|E| log OP T CESD (S(G), r))-time algorithm (see sections 2 and 4 from [7]).

We call a subset V ⊆ V by a vertex cover for G = (V, E) when e ∩ V = ∅ for any e ∈ 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. 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 + d max 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(|E| 1+ε )-time constant factor approximation algorithm is given in [6] to approximate the Hitting Set problem for sets of objects whose generalized aspect ratio is bounded from above by some constant.

Conclusion

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.