=Paper=
{{Paper
|id=Vol-1894/mpr2
|storemode=property
|title=Intersecting straight line segments with disks: complexity and approximation
|pdfUrl=https://ceur-ws.org/Vol-1894/mpr2.pdf
|volume=Vol-1894
|authors=Konstantin S. Kobylkin
}}
==Intersecting straight line segments with disks: complexity and approximation==
https://ceur-ws.org/Vol-1894/mpr2.pdf
Intersecting straight line segments with disks:
complexity and approximation
Konstantin S. Kobylkin
kobylkinks@gmail.com
Krasovskii Institute of Mathematics and Mechanics (Yekaterinburg, Russia)
Ural Federal University (Yekaterinburg, Russia)
Abstract
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 ∈
[dmin , ηdmax ] and some constant η where dmax and dmin are Euclidean
lengths of the longest and shortest graph edges respectively. Fast
O(|E| log |E|)-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.
1 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 Rd and a set U ⊆ Rd , find the smallest cardinality set
H ⊆ U such that N ∩ H 6= ∅ 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 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 ∈ 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 := Nr (E) = {Nr (e)}e∈E and U := R2 where Nr (e) =
Br (0) + e = {x + y : x ∈ Br (0), y ∈ e} 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
1 a graph without loops and parallel edges
209
Br (x) is the disk of radius r centered at x ∈ R2 . 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 ∈ [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 [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 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) 2r where d(e) is the length of the edge e.
APX-hardness of the discrete3 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 T 4 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 ∈ [dmin , dmax ]
and µ = ddmaxmin
= O(n) where n = |S|. IPGD remains strongly NP-hard within the class of nearest neighbour
graphs for r ∈ [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.
3
The upper bound on µ for Delaunay triangulations is comparable with the lower bound µ = Ω n2 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 Nr (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 Nr (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 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 [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:
|CA (G, r)|
≤ f,
OP TIP GD (G, r)
where CA (G, r) is a feasible solution to IPGD output by A for a given plane graph G and radius r
whereas OP TIP 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
2 int N is the set of interior points of N
3 when U coincides with some prescribed finite set
4 bd T denotes the set of boundary points of T
210
by some linear function of r, or, in other words, when objects from Nr (E) have their aspect ratio bounded from
above by 1 + λ.
2 Hardness results
We give complexity analysis for the IPGD problem by first considering its setting where r ∈ [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 µ = ddmax min
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 ∈ V0 \V00 there is some v = v(u) ∈ 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 [10] strong NP-hardness of CDC is proved by
reduction from the minimum dominating set problem. This reduction involves using plane orthogonal drawing of
G0 on some integer grid. More specifically, a set D is build on that grid with V0 ⊂ D. The resulting hard instance
of the CDC problem is for the set D and some integer (constant) radius r0 ≥ 1. Let us observe that G0 admits
an orthogonal drawing (theorem 1 [14]) on the grid of size O(|V0 |) × O(|V0 |) whereas total length of each edge is
O(|V0 |). 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
r0 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 r0 disks to be at the points of D.
Remark 1. For every simple planar graph G0 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 D0 ⊂ D iff a slightly larger disk intersects straight line segments, each of which is close to some point
of D0 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 ⊂ Z2 , 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
1
min ρ(u; v, w) ≥
u∈C(v,w),v6
/ =w,u,v,w∈X,|v−w|2 ≤2r 480r5
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
S set C ⊂ R2 such that each e ∈ E is within (Euclidean) distance r from
some point c = c(e) ∈ C and C ⊂ Bδ (v).
v∈V
211
Theorem 2. Both IPGD and VRIPGD(δ) problems are strongly NP-hard for r ∈ [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 δ = 200012 2r11 . For every u ∈ D points u0 and v0 are found such that |u − u0 |∞ ≤ δ/2
0
and |u − v0 |∞ ≤ δ/2 where Iu = [u0 , v0 ] has Euclidean length at least δ/2. More specifically, let us set ID =
{Iu = [u0 , v0 ] : u ∈ D}. 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 ∪ {Iu }, D0 ⊂ D, where segments of ID0 are already defined. Here endpoints of Iu are chosen in the rational
c1 c1
grid that contains u whose elementary square size is |D| 2 × |D|2 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 |D|. Obviously, each segment Iu coincides with some edge from E.
We have dmin ≤ r and µ = O(|S|). It remains to prove that r ≤ dmax . 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 ≤ dmax 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 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 = {Iu : u ∈ D0 } of segments for some D0 ⊆ D. When |D0 | = 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
q q
|O − u3 |2 + |O − O0 |2 − r0 ≤ 2δ + (r0 + 2δ)2 − δ12 − r02 − δ12 =
4r0 δ + 4δ 2 p 1
= 2δ + p ≤ 2δ + 2 r0 δ + δ 2 < ,
480r05
p
(r0 + 2δ)2 − δ12 + r02 − δ1
2
where δ1 = |u1 −u2
2 |2
≤ 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. √
3
Using corollary 1 of section 4.2 from [1] and theorem 1 from [12] we arrive at the lower bound µ = Ω n2
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 6= 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.
212
The proof of theorem 2 is extendable for classes of Gabriel, relative neighbourhood and nearest neighbour
graphs. It is easy to observe that segments Iu , 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 ∈ [dmin , dmax ], µ = O(n) and
δ = Θ(r) within classes of Gabriel, relative neighbourhood graphs and minimum Euclidean spanning trees and
for r ∈ [dmax , ηdmax ] 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]).
3 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 Nr (E). More specifically, let us focus on the case of IPGD where
the inequality r ≥ dmax2λ 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(|E| log OP TCESD (S(G), r))-time algorithm (see sections 2 and 4 from [7]).
We call a subset V 0 ⊆ V by a vertex cover for G = (V, E) when e ∩ V 0 6= ∅ 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.
Statement 1. The following bound holds true for any graph G ∈ Gλ without isolated vertices:
OP TCESD (S(G), r)
≤ p(1 + 2λ)
OP TIP GD (G, r)
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 ∈ Gλ . Set E(c, G) := {e ∈ E : c ∈
Nr (e)}, c ∈ C0 . For every e ∈ E(c, G) there is a point c(e) ∈ e with |c − c(e)|2 ≤ 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 S of p,
at most p(1 + 2λ) radius r disks are needed to cover radius r + dmax disk. Therefore the set S(G) ⊆ S(c, G)
c∈C0
is contained in the union of at most |C0 |p(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(|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.
4 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.
Acknowledgements
Our work was supported by the Russian Science Foundation, project № 14-11-00109.
213
References
[1] Esther M. Arkin, Antonio Fernandez Anta, Joseph S. B. Mitchell, and Miguel A. Mosteiro. Probabilistic
bounds on the length of a longest edge in Delaunay graphs of random points in d dimensions. Comput.
Geom., 48(2):134–146, 2015.
[2] Prosenjit Bose, Jean-Lou De Carufel, Stephane Durocher, and Perouz Taslakian. Competitive online routing
on Delaunay triangulations. In R. Ravi and Inge Li Gortz, editors, SWAT, volume 8503 of Lecture Notes in
Computer Science, pages 98–109. Springer, 2014.
[3] P. Bose, P. Morin, I. Stojmenović, J. Urrutia. Routing with guaranteed delivery in ad hoc wireless networks.
Wireless Networks, 7(6):609–616, 2001.
[4] Timothy M. Chan and Elyot Grant. Exact algorithms and APX-hardness results for geometric packing and
covering problems. Comput. Geom., 47(2):112–124, 2014.
[5] S. Dasgupta, C.H. Papadimitriou and U.V. Vazirani. Algorithms. McGraw-Hill, 2006.
[6] Alon Efrat, Matthew J. Katz, Frank Nielsen, Micha Sharir. Dynamic data structures for fat objects and
their applications. Computational Geometry, 15:215–227, 2000.
[7] Teofilo F. Gonzalez. Covering a set of points in multidimensional space. Inf. Process. Lett., 40(4):181–188,
1991.
[8] S. Har-Peled, K. Quanrud. Approximation algorithms for polynomial-expansion and low-density graphs. In
Nikhil Bansal and Irene Finocchi, editors, ESA, volume 9294 of Lecture Notes in Computer Science, pages
717–728. Springer, 2015.
[9] Daniel Marx. Efficient approximation schemes for geometric problems? In Gerth Stolting Brodal and Stefano
Leonardi, editors, ESA, volume 3669 of Lecture Notes in Computer Science, pages 448–459. Springer, 2005.
[10] Sh. Masuyama, T. Ibaraki, T. Hasegawa. Computational complexity of the m-center problems on the plane.
Transactions of the Institute of Electronics and Communication Engineers of Japan. Section E, E64(2):57–
64, 1981.
[11] E. Pyrga, S. Ray. New existence proofs for ε-nets. Proceedings of the twenty-fourth annual symposium on
Computational geometry, 199–207, 2008.
[12] Takuji Onoyama, Masaaki Sibuya, and Hiroshi Tanaka. Limit Distribution of the Minimum Distance
between Independent and Identically Distributed d-Dimensional Random Variables, pages 549–562. Springer
Netherlands, Dordrecht, 1984.
[13] Joseph O’Rourke. Art Gallery Theorems and Algorithms. Oxford University Press, 1987.
[14] R. Tamassia, I.G. Tollis. Planar grid embedding in linear time. IEEE Transactions on Circuits and Systems,
36:1230–1234, 1989.
214