11institutetext: Institute of Mathematics and Mechanics, Ural Branch of RAS,
Sophya Kovalevskaya str. 16, 620990 Ekaterinburg, Russia,
Ural Federal University, Mira str. 19, 620002 Ekaterinburg, Russia,
<EMAIL_ADDRESS>
Konstantin Kobylkin

# Stabbing line segments with disks: complexity and approximation algorithms
111This work was supported by Russian Science Foundation, project
№14-11-00109.

Konstantin Kobylkin

###### Abstract

Computational complexity and approximation algorithms are reported for a
problem of stabbing a set of straight line segments with the 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. Close
geometric problems arise in network security applications. We give 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 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\geq\eta d_{\max}$ holds uniformly for some constant
$\eta>0,$ i.e. when lengths of edges of $G$ are uniformly bounded from above
by some linear function of $r.$

###### Keywords:

computational complexity, approximation algorithms, Hitting Set, Continuous
Disk Cover, Delaunay triangulations

##  1 Introduction

Numerous applications from security, sensor placement and robotics lead to
computational geometry problems in which one needs to find the smallest
cardinality set $C$ of points on the plane having bounded (in some sense)
visibility area such that each piece of the boundary of a given geometric
object or any part of the complex (i.e. set of edges or faces) of a plane
graph is within visibility area of some point from $C,$ see e.g. [5], [12].
Refining complexity statuses and designing approximation algorithms for these
problems is still an area of active research. In this paper complexity and
approximability are studied of the following problem.

Intersecting Plane Graph with Disks (IPGD): given a straight line drawing (or
a plane graph) $G=(V,E)$ of an arbitrary simple222a graph without loops and
parallel edges planar graph without edge crossings and a constant $r>0,$ find
the smallest cardinality set $C\subset\mathbb{R}^{2}$ of points (disk centers)
such that each edge $e\in E$ is within Euclidean distance $r$ from some point
$c=c(e)\in C$ or, equivalently, the disk of radius $r$ centered at $c$
intersects $e.$

The IPGD abbreviation is used throughout our paper to denote the above problem
for simplicity of presentation.

Applications of complexity and algorithmic analysis of the IPGD problem come
from network security. More specifically, IPGD represents the following model
in which we are to evaluate vulnerability of some physical network to
simultaneous technical failures caused by natural (e.g. floods, fire,
electromagnetic pulses) and human sources. In this model network nodes are
modeled by points on the plane while its physical links are given in the form
of straight line segments. A catastrophic event (threat) is usually localized
in a particular geographical area and modeled by a disk of some fixed radius
$r>0.$ A threat impacts a network link when the corresponding disk and segment
intersect. Evaluation of the network vulnerability can be posed in the form of
finding the minimum number of threats along with their positions that cause
all network links to be broken. Thus, it brings us to the IPGD problem
assuming that network links are geographically non-overlapping. A similar
setting is considered in [1] with the fixed number of threats. Furthermore, in
[12] a close geometric problem is considered called the Art Gallery problem
where point coverage area is affected by boundaries of its neighbouring
geometric objects whereas point has circular visibility area in the case of
the IPGD problem.

In this paper computational complexity and approximability of IPGD are studied
for simple plane graphs with either $r\in[d_{\min},d_{\max}]$ or
$r=\Omega(d_{\max})$ where $d_{\max}$ and $d_{\min}$ are Euclidean 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, some of their connected subgraphs, e.g. for Gabriel
graphs. These graphs are often called proximity graphs. Delaunay
triangulations are plane graphs which admit efficient geometric routing
algorithms [4], thus, representing convenient network topologies. Gabriel
graphs arise in modeling wireless networks [14].

###  1.1 Related work

IPGD is related to several well-known combinatorial optimization problems.
First, we have the Continuous Disk Cover (CDC) problem for the case of IPGD
where $G$ consists of isolated vertices, i.e. when segments from $E$ are all
of zero length. Strong NP-hardness is well known for CDC [9]. Second, IPGD
coincides with known Vertex Cover problem for $r=0.$ Third, it is the special
case of the geometric Hitting Set problem on the plane.

Hitting Set: given a family ${\cal{N}}$ of sets on the plane and a set
$U\subseteq\mathbb{R}^{2},$ find the smallest cardinality set $H\subseteq U$
such that $N\cap H\neq\varnothing$ for every $N\in{\cal{N}}.$

IPGD coincides with Hitting Set if we set
${\cal{N}}:={\cal{N}}_{r}(E)=\\{N_{r}(e)\\}_{e\in E}$ and $U:=\mathbb{R}^{2}$
where $N_{r}(e)=B_{r}(0)+e=\\{x+y:x\in B_{r}(0),\,y\in 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\in\mathbb{R}^{2}.$ An aspect ratio of a
closed convex set $N$ with
${\mathrm{int}}\,N\neq\varnothing$333${\mathrm{int}}\,N$ is the set of
interior points of $N$ 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 set $N_{r}(e)$ (also called by object in the sequel)
has aspect ratio equal to $1+\frac{d(e)}{2r}$ where $d(e)$ is Euclidean length
of edge $e\in E.$ APX-hardness of the discrete444when $U$ coincides with some
prescribed finite set Hitting Set problem is presented for families of axis-
parallel rectangles, generally, with unbounded aspect ratio, [6], and for
families of triangles of bounded aspect ratio [13].

###  1.2 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 four
of which are cocircular. We call a plane graph $G=(S,E)$ a Delaunay
triangulation if $[u,v]\in E$ iff there is a disk $T$ such that
$u,v\in{\rm{bd}}\,T$555${\rm{bd}}\,T$ denotes the set of boundary points of
$T$ and $S\cap{\rm{int}}\,T=\varnothing.$ Finally, a plane graph $G=(S,E)$ is
named a nearest neighbour graph when $[u,v]\in E$ iff either $u$ or $v$ is the
nearest Euclidean neighbour for $v$ or $u$ respectively.

####  1.2.1 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 and relative neighbourhood graphs) for $r\in[d_{\min},d_{\max}]$ and
$\mu=\frac{d_{\max}}{d_{\min}}=O(|S|).$ IPGD remains strongly NP-hard within
the class of nearest neighbour graphs for $r\in[d_{\max},\eta d_{\max}]$ with
a large constant $\eta$ and $\mu\leq 4.$ Furthermore, we have the same NP-
hardness results under the same restrictions on $r$ and $\mu$ even if we are
bound to choose points of $C$ close to vertices of $G.$ The upper bound on
$\mu$ for Delaunay triangulations is comparable with the lower bound
$\mu=\Omega\left(\sqrt[3]{n^{2}}\right)$ which holds true with positive
probability for Delaunay triangulations produced by $n$ random independent
points on the unit disk [2]. Thus, declared restrictions on $r$ and $\mu$
define natural instances of IPGD.

An upper bound on $\mu$ implies an upper bound on the ratio of the largest and
smallest aspect ratio of objects from ${\cal{N}}_{r}(E).$ The Hitting Set
problem is generally easier when sets from ${\cal{N}}$ have almost equal
aspect ratio bounded from above by some constant. Our result for the class of
nearest neighbour graphs gives the problem NP-hardness in the case where
objects of ${\cal{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
${\cal{N}}_{r}(E)$ formed by an edge set of a specific plane graph; each set
from ${\cal{N}}_{r}(E)$ is of the special form of Minkowski sum of some graph
edge and radius $r$ disk. Our proofs are elaborate complexity reductions from
the CDC problem which is intimately related to IPGD.

####  1.2.2 Positive results.

Let $R(E)$ be the smallest radius of the disk that intersects all segments
from the edge set $E.$ As opposed to the cases where either
$r\in[d_{\min},d_{\max}]$ or $r\in[d_{\max},\eta d_{\max}],$ IPGD is solvable
within the class of simple plane graphs, for which the inequality $r\geq\eta
R(E)$ holds uniformly for some fixed $\eta>0,$ in
$O\left(k^{2}|E|^{2k+1}\right)$ time with
$k=\left\lceil\frac{\sqrt{2}}{\eta}\right\rceil^{2}.$ Above inequality implies
an upper bound $k$ on its optimum. Taking proof of $W[1]$-hardness into
account of parameterized version of CDC [10] as well as the reduction used to
prove the theorem 2.2 of this paper, it seems unlikely to improve this time
bound to $O(f(k)|E|^{c})$ for any computable function $f$ and any constant
$c>0.$

Finally, we present an $8p(1+2\lambda)$-approximation $O(|E|\log|E|)$-time
algorithm for IPGD when the inequality $r\geq\frac{d_{\max}}{2\lambda}$ holds
true uniformly within a class of simple plane graphs for a constant
$\lambda>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 uniformly bounded from above by some linear function of
$r,$ or, in other words, when objects from ${\cal{N}}_{r}(E)$ have their
aspect ratio bounded from above by $1+\lambda.$ A similar but more complex
$O(|E|^{1+\varepsilon})$-time constant factor approximation algorithm is given
in [7] to approximate the Hitting Set problem for sets of objects whose aspect
ratio is bounded from above by some constant.

##  2 NP-hardness results

We give complexity analysis for the IPGD problem by considering its setting
where $r\in[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
${\cal{N}}_{r}(E)$ of Euclidean $r$-neighbourhoods of edges of $G.$ For the
IPGD problem we claim its 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 $\mu=\frac{d_{\max}}{d_{\min}}$ bounded from above, thus, imposing an
upper bound on the ratio of the largest and smallest aspect ratio of objects
from ${\cal{N}}_{r}(E).$ We show that IPGD remains intractable even in its
simple case where $r=\Theta(d_{\max})$ and $\mu$ is bounded by some small
constant or, equivalently, when objects of ${\cal{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 $\mu.$

###  2.1 NP-hardness of the CDC problem

To single out the class of hard instances of the CDC problem a reduction is
used in [9] 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^{\prime}_{0}\subseteq
V_{0}$ such that for each $u\in V_{0}\backslash V^{\prime}_{0}$ there is some
$v=v(u)\in V^{\prime}_{0}$ which is adjacent to $u.$

Below an integer grid denotes the set of all points on the plane with integer-
valued coordinates each of which belongs to 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 that are composed of connected axis-parallel
straight line segments of the form
$[p_{1},p_{2}],\,[p_{2},p_{3}],\ldots,\,[p_{k-1},p_{k}],$ and intersecting
only at the edge endpoints $p_{1}$ and $p_{k},$ where each point $p_{i}$ again
belongs to the grid. In [9] 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}\subset D.$ The resulting hard instance
of the CDC problem is for the set $D$ and some integer (constant) radius
$r_{0}\geq 1.$ Let us observe that $G_{0}$ admits an orthogonal drawing
(theorem 1 [15]) on the grid of size $O(|V_{0}|)\times O(|V_{0}|)$ whereas
total length of each edge is of the order $O(|V_{0}|).$ Proof of strong NP-
hardness of CDC could be conducted taking into account this observation. We
can formulate (see theorems 1 and 3 from [9])

###### Theorem 2.1

[9] 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|)\times 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.

###  2.2 NP-hardness of the IPGD problem for Delaunay triangulations

To build a reduction from the CDC problem on the set $D$ (as constructed in
proof of the theorem 2.1 from [9]), we exploit a simple idea that a radius $r$
disk covers a set of points $D^{\prime}\subset D$ iff a slightly larger disk
intersects (and, sometimes, covers) straight line segments, each of which is
close to some point of $D^{\prime}$ 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 NP-hardness for the IPGD problem within numerous
classes of proximity graphs. The following technical lemma holds which reports
an $r$-dependent lower bound on the distance between any point with integer
coordinates and a radius $r$ circle through the pair of integer-valued points.

###### Lemma 1

Let $X\subset\mathbb{Z}^{2},$ $r\geq 1$ is an integer, $\rho(u;v,w)$ denotes
the minimum of two Euclidean distances from an arbitrary point $u\in X$ to the
union of two radius $r$ circles which pass through distinct points $v$ and $w$
from $X,$ where $|v-w|_{2}\leq 2r,$ $\mathbb{Z}$ is the set of integers and
$|\cdot|_{2}$ is Euclidean norm. Then

$\min\limits_{u\notin C(v,w),\,v\neq w,\,u,v,w\in X,\,|v-w|_{2}\leq
2r}\rho(u;v,w)\geq\frac{1}{480r^{5}},$

where $C(v,w)$ is the union of two radius $r$ circles passing through $v$ and
$w.$

Let us formulate the following restricted form of IPGD.

Vertex Restricted IPGD (VRIPGD($\delta$)): given a simple plane graph
$G=(V,E),$ a constant $\delta>0$ and a constant $r>0,$ find the least
cardinality set $C\subset\mathbb{R}^{2}$ such that each $e\in E$ is within
Euclidean distance $r$ from some point $c=c(e)\in C$ and
$C\subset\bigcup\limits_{v\in V}B_{\delta}(v).$

###### Theorem 2.2

Both IPGD and VRIPGD$(\delta)$ problems are strongly NP-hard for
$r\in[d_{\min},d_{\max}],\,\mu=O(n)$ and $\delta=\Theta(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($\delta$) problem is analogous taking into account the theorem 2.1 (see
also proof of the theorem 3 from [9] for details). For any hard instance of
the CDC problem, which the theorem 2.1 reports, the IPGD problem instance is
built for $r=r_{0}+\delta$ and $\delta=\frac{1}{2000^{2}2r_{0}^{11}}$ as
follows. For every $u\in D$ points $u_{0}$ and $v_{0}$ are found such that
$|u-u_{0}|_{\infty}\leq\delta/2$ and $|u-v_{0}|_{\infty}\leq\delta/2,$ where
$I_{u}=[u_{0},v_{0}]$ has Euclidean length at least $\delta/2$ and
$|\cdot|_{\infty}$ denotes norm in $\mathbb{R}^{2}$ equal to the maximum of
absolute values of vector coordinates. More specifically, let us set
$I_{D}=\\{I_{u}=[u_{0},v_{0}]:u\in D\\}.$ Endpoints of segments from $I_{D}$
are constructed in sequential manner in polynomial time and space by defining
a new segment $I_{u}$ to provide general position for the set of endpoints of
the set $I_{D^{\prime}}\cup\\{I_{u}\\},\,D^{\prime}\subset D,$ where segments
of $I_{D^{\prime}}$ are already defined. Here endpoints of $I_{u}$ are chosen
in the rational grid that contains $u$ whose elementary cell size is
$\frac{c_{1}}{|D|^{2}}\times\frac{c_{1}}{|D|^{2}}$ for some small absolute
rational constant $c_{1}=c_{1}(\delta).$ 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}-\delta/4$ whereas $v_{0}$ is taken from the upper one for which
$y$-coordinates exceed $u_{y}+\delta/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}\leq r$ and
$\mu=O(|S|).$ It remains to prove that $r\leq d_{\max}.$ Due to the remark 1
and a construction of the set $D$ (see fig. 1 and proof of the theorem 1 from
[9]) the set $S$ can be constructed such that the inequality $r\leq 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^{\prime}}=\\{I_{u}:u\in D^{\prime}\\}$ of segments for some
$D^{\prime}\subseteq D.$ When $|D^{\prime}|=1,$ it is easy to transform $T$
into a disk which contains the segment $I_{D^{\prime}}.$ Points of $D$ have
integer coordinates. Moreover, squared Euclidean distance between each pair of
points of the subset $D^{\prime}$ does not exceed
$(2r_{0}+4\delta)^{2}=4r_{0}^{2}+16r_{0}\delta+16\delta^{2}.$ As
$r_{0}\in\mathbb{Z},$ points from $D^{\prime}$ 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^{\prime}.$ 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\leq
r_{0}+2\delta.$ Let us show that the case $R>r_{0}$ is void. The center of
$T_{0}$ can be shifted 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^{\prime}.$ The distance from the point $u_{3}$ to the radius $r_{0}$ circle
centered at $O^{\prime}$ does not exceed

$|O-u_{3}|_{2}+|O-O^{\prime}|_{2}-r_{0}\leq
2\delta+\sqrt{(r_{0}+2\delta)^{2}-\delta_{1}^{2}}-\sqrt{r_{0}^{2}-\delta_{1}^{2}}=$
$=2\delta+\frac{4r_{0}\delta+4\delta^{2}}{\sqrt{(r_{0}+2\delta)^{2}-\delta_{1}^{2}}+\sqrt{r_{0}^{2}-\delta_{1}^{2}}}\leq
2\delta+2\sqrt{r_{0}\delta+\delta^{2}}<\frac{1}{480r_{0}^{5}},$

where $\delta_{1}=\frac{|u_{1}-u_{2}|_{2}}{2}\leq r_{0}.$ By the lemma 1 we
have $R\leq r_{0}.$ Thus, $D^{\prime}$ is contained in some disk of radius
$r_{0}.$ Given a set of points on the plane, 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.$

Using the corollary 1 of section 4.2 from [2] and the theorem 1 from [11] we
arrive at the lower bound $\mu=\Omega\left(\sqrt[3]{n^{2}}\right)$ 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 $\mu$
for the considered class of hard instances of the IPGD problem is comparable
with the one for random Delaunay triangulations.

###  2.3 NP-hardness of IPGD for other classes of proximity graphs

The same proof technique could be applied for proving NP-hardness of the
problem 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 when
$[u,v]\in 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]\in E$ iff
there is no any other point $w\in S$ such that $w\neq 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 Euclidean distance between the edge
endpoints.

###### Corollary 1

Both IPGD and VRIPGD$(\delta)$ problems are strongly NP-hard for
$r\in[d_{\min},d_{\max}],\,\mu=O(n)$ and $\delta=\Theta(r)$ within classes of
Gabriel, relative neighbourhood graphs and minimum Euclidean spanning trees as
well as for $r\in[d_{\max},\eta d_{\max}]$ and $\mu\leq 4$ within the class of
nearest neighbour graphs where $\eta$ is a large constant.

##  3 Positive results

###  3.1 Polynomial solvability of the IPGD problem for large $r$

Before presenting polynomially solvable case of the IPGD problem we are to
take some preprocessing. It is aimed at reducing the set of points, among
which centers of radius $r$ disks are chosen, to a finite set whose
cardinality is bounded from above by some polynomial in $|E|.$

####  3.1.1 Problem preprocessing.

As was mentioned in the Introduction, the IPGD problem coincides with the
Hitting Set problem considered for Euclidean $r$-neighbourhoods of graph edges
which form the system denoted by ${\cal{N}}_{r}(E).$ Their boundaries are
composed of four parts: two half-circles and two parallel straight line
segments. W.l.o.g. we can assume that intersection of any subset of objects
from ${\cal{N}}_{r}(E)$ (if nonempty) contains a point from the intersection
of boundaries of two objects from ${\cal{N}}_{r}(E).$ Thus, our choice of
points to form a feasible solution to the IPGD problem can be restricted to
the set of intersection points of boundaries of pairs of objects from
${\cal{N}}_{r}(E).$ The following lemma can be considered a folklore.

###### Lemma 2

Let $G=(V,E)$ be a simple plane graph. Each feasible solution $C$ to the IPGD
problem for $G$ can be converted in polynomial time and space (in $|E|)$ to a
feasible solution $D\subset D_{r}(G)$ to IPGD for $G$ with $|D|\leq|C|,$ where
$D_{r}(G)\subset\mathbb{R}^{2}$ is some set of cardinality of the order
$O(|E|^{2})$ which can be constructed in polynomial time and space.

####  3.1.2 Polynomially solvable case of IPGD.

In distinction to the cases where either $r\in[d_{\min},d_{\max}]$ or
$r=\Theta(d_{\max})$ the IPGD problem is polynomially solvable for
$r=\Omega(R(E))$ where $R(E)$ is the smallest radius of the disk that
intersects all segments from $E.$ Due to [3] the IPGD problem is solvable in
$O(|E|)$ time within the class of plane graphs for which the inequality $r\geq
R(E)$ holds uniformly.

Let us consider the IPGD problem within the class of plane graphs for which
the inequality $r\geq\eta R(E)$ holds uniformly for some fixed constant
$0<\eta<1.$ Since every radius $r$ disk contains an axis-parallel rectangle
whose side is equal to $r\sqrt{2},$ roughly at most
$\left\lceil\frac{\sqrt{2}R(E)}{r}\right\rceil^{2}\leq\left\lceil\frac{\sqrt{2}}{\eta}\right\rceil^{2}=k(\eta)=k$
radius $r$ disks are needed to intersect all segments from $E.$ Therefore the
brute-force search algorithm could be applied that just sequentially tries
each subset of $D_{r}(G)$ of cardinality at most $k.$ This amounts roughly to
$O\left(k^{2}|E|^{2k+1}\right)$ time complexity. Thus, we arrive at the
polynomial time algorithm whose complexity depends exponentially on $1/\eta.$
This algorithm gives an optimal solution to the IPGD problem taking the lemma
2 into account.

###  3.2 Approximation algorithm for the IPGD problem

Below the approximation algorithm is reported for the IPGD problem whose
approximation factor depends on the maximum aspect ratio among objects of
${\cal{N}}_{r}(E).$ More specifically, let us focus on the case of IPGD where
the inequality $r\geq\frac{d_{\max}}{2\lambda}$ holds uniformly within some
class ${\cal{G}}_{\lambda}$ of simple plane graphs for a constant $\lambda>0.$
It corresponds to the situation where objects from the system
${\cal{N}}_{r}(E)$ have their aspect ratio bounded from above by $1+\lambda.$
In this case it turns out that the problem admits an $O(1)$-approximation
algorithm whose factor depends on $\lambda.$ The following auxiliary problem
is considered to formulate it.

Cover endpoints of segments with disks (CESD). Let $S(G)\subseteq 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\,{OPT_{CESD}(S(G),r)})$-time algorithm (see sections 2 and 4
from [8]).

We call a subset $V^{\prime}\subseteq V$ by a vertex cover for $G=(V,E)$ when
$e\cap V^{\prime}\neq\varnothing$ for any $e\in 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 3.1

The following bound holds true for any graph $G\in{\cal{G}}_{\lambda}$ without
isolated vertices:

$\frac{OPT_{CESD}(S(G),r)}{OPT_{IPGD}(G,r)}\leq p(1+2\lambda)$

where $p(x)$ is the smallest number of unit disks needed to cover radius $x$
disk.

###### Proof

Let $C_{0}=C_{0}(G,r)\subset\mathbb{R}^{2}$ be an optimal solution to IPGD for
a given $G\in{\cal{G}}_{\lambda}.$ Set $E(c,G):=\\{e\in E\colon c\in
N_{r}(e)\\},\,c\in C_{0}.$ For every $e\in E(c,G)$ there is a point $c(e)\in
e$ with $|c-c(e)|_{2}\leq r.$ Any point from the set $S(c,G)$ of endpoints of
segments from $E(c,G)$ is within the distance $r+d_{\max}$ from the point $c.$
Due to definition of $p,$ at most $p(1+2\lambda)$ radius $r$ disks are needed
to cover содержит radius $r+d_{\max}$ disk. Therefore the set
$S(G)\subseteq\bigcup\limits_{c\in C_{0}}S(c,G)$ is contained in the union of
at most $|C_{0}|p(1+2\lambda)$ radius $r$ disks.

###### Corollary 2

The algorithm is $8p(1+2\lambda)$-approximate.

###### Remark 2

Approximation factor of the algorithm is in fact lower when
${\cal{G}}_{\lambda}$ is the subclass of Delaunay triangulations or of 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+\lambda)$-approximate.

##  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 plane graph. It is shown that the problem is strongly NP-
hard within the class of Delaunay triangulations and some of their subgraphs
for small and medium values of $r$ while for large $r$ it is polynomially
solvable. Fast approximation algorithm is given for the IPGD problem whose
approximation factor depends on the maximum aspect ratio among objects from
${\cal{N}}_{r}(E).$ Of course, those algorithms are of particular interest
whose factor is bounded from above by some absolute constant. This sort of
algorithms is our special focus for future research.

## References

  * [1] P. K. Agarwal, A. Efrat, S. K. Ganjugunte, D. Hay, S. Sankararaman, G. Zussman.  The resilience of WDM networks to probabilistic geographical failures.  IEEE/ACM Trans. Netw., 21(5):1525–1538, 2013.
  * [2] E. M. Arkin, A. F. Anta, J. S. Mitchell, M. 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.
  * [3] B. K. Bhattacharya, S. Jadhav, A. Mukhopadhyay, J. M. Robert.  Optimal algorithms for some intersection radius problems.  Computing, 52(3):269–279, 1994.
  * [4] P. Bose, J.L. De Carufel, S. Durocher, P. Taslakian.  Competitive online routing on Delaunay triangulations.  Lecture Notes in Computer Science, 8503:98–109, 2014.
  * [5] P. Bose, D. G. Kirkpatrick, Z. Li.  Worst-case-optimal algorithms for guarding planar graphs and polyhedral surfaces.  Comput. Geom., 26(3):209–219, 2003.
  * [6] T. M. Chan, E. Grant.  Exact algorithms and APX-hardness results for geometric packing and covering problems.  Comput. Geom., 47(2):112–124, 2014.
  * [7] A. Efrat, M.J. Katz, F. Nielsen, M. Sharir.  Dynamic data structures for fat objects and their applications.  Comput. Geom., 15:215–227, 2000.
  * [8] T. F. Gonzalez.  Covering a set of points in multidimensional space.  Inf. Process. Lett., 40(4):181–188, 1991.
  * [9] T. Hasegawa, S. Masuyama, T. Ibaraki.  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.
  * [10] D. Marx.  Efficient approximation schemes for geometric problems?  Lecture Notes in Computer Science, 3669:448–459, 2005.
  * [11] T. Onoyama, M. Sibuya, H. Tanaka.  Limit Distribution of the Minimum Distance between Independent and Identically Distributed $d$-Dimensional Random Variables.  Statistical Extremes and Applications, 549–562, 1984.
  * [12] J. O’Rourke.  Art Gallery Theorems and Algorithms.  Oxford University Press, 1987.
  * [13] K. Quanrud, S. Har-Peled.  Approximation algorithms for polynomial-expansion and low-density graphs.  Lecture Notes in Computer Science, 9294:717–728, 2015.
  * [14] I. Stojmenovic, J. Urrutia, P. Bose, P. Morin.  Routing with guaranteed delivery in ad hoc wireless networks.  Wireless Networks, 7(6):609–616, 2001.
  * [15] R. Tamassia, I.G. Tollis.  Planar grid embedding in linear time.  IEEE Transactions on Circuits and Systems, 36:1230–1234, 1989.

##  Appendix 0.A Proof of the Lemma 1

###### Proof

Let $u=(x,y),\,v=(x_{1},y_{1})$ and $w=(x_{2},y_{2})$ be distinct points of
$X.$ Consider an arbitrary radius $r$ circle (out of two circles) which passes
through $v$ and $w,$ and denote its center by $O.$ A lower bound is obtained
below for the distance $\pi=\pi(u;v,w)$ from that circle to the point $u\notin
C(v,w).$

Let $\Delta=|v-w|_{2},$ $\lambda=\sqrt{r^{2}-\frac{\Delta^{2}}{4}}$,
$a=(u-v,u-w)$ and $b=(u-v,(v-w)^{\perp})$, where
$(v-w)^{\perp}=\pm(y_{1}-y_{2},-x_{1}+x_{2})$. The distance $\pi>0$ can be
written in the form:

$\pi=\pi(u;v,w)=\left|\left|\frac{v+w}{2}-\lambda\frac{(v-w)^{\perp}}{|v-w|_{2}}-u\right|_{2}-r\right|=\left|\frac{a+\frac{{2\lambda
b}}{\Delta}}{\sqrt{a+\frac{{2\lambda b}}{\Delta}+r^{2}}+r}\right|.$

Without loss of generality it assumed that $u$ is in the $2r$ radius disk
centered at $O$. Indeed, otherwise $\pi\geq r\geq\frac{1}{r}$. Let us bound
denominator of fraction $\pi,$ taking into account that $\Delta\leq 2r,$
$|u-v|_{2}\leq|u-O|_{2}+|O-v|_{2}\leq 3r$ and $|b|/\Delta\leq 3r:$

$\sqrt{a+\frac{2\lambda b}{\Delta}+r^{2}}+r\leq 5r.$

As points of $X$ have integer coordinates, $a$ and $b$ are integers. For
$\Delta^{2}=4r^{2}$ we get $\pi\geq\frac{1}{5r}$. When $\Delta^{2}\leq
4r^{2}-1$ it is enough to prove the inequality

$\left|a+\frac{2\lambda b}{\Delta}\right|\geq\frac{1}{96r^{4}}.$

Indeed, again, combining this bound with the aforementioned upper bound for
denominator of the fraction $\pi,$ we get $\pi\geq\frac{1}{480r^{5}}$.

For integer $\frac{2\lambda b}{\Delta}$ the left-hand side of the inequality
is at least 1. Thus, it remains for us to prove the inequality for the case
where $\frac{2\lambda b}{\Delta}\notin\mathbb{Z}$. Suppose that
$q=\left\\{\left|\frac{2\lambda b}{\Delta}\right|\right\\}>0$ and
$k=\left[\left|\frac{2\lambda b}{\Delta}\right|\right],$ where $\\{\cdot\\}$
and $[\cdot]$ denote fractional and integer part of real number respectively.
In fact, the term $\min\\{q,1-q\\}$ is bounded from below. Let us start
estimating with $q.$ First, it is assumed that
$\gamma=\frac{4r^{2}b^{2}}{\Delta^{2}}\in~{}\mathbb{Z}.$ We have
$k^{2}<\frac{4\lambda^{2}b^{2}}{\Delta^{2}}<(k+1)^{2}.$ As $q>0,$ we get
$q\geq\left\\{\sqrt{k^{2}+1}\right\\}.$ Due to concavity of the square root we
have

$\left\\{\sqrt{k^{2}+1}\right\\}=\left\\{\sqrt{\frac{2k\cdot
k^{2}}{2k+1}+\frac{(k+1)^{2}}{2k+1}}\right\\}\geq\left\\{k+\frac{1}{2k+1}\right\\}=\frac{1}{2k+1}\geq$
$\geq\frac{1}{\frac{4\lambda|b|}{\Delta}+1}\geq\frac{1}{13r^{2}}.$

Now the case is considered where $\gamma\notin\mathbb{Z}$. As
$2kq+q^{2}\geq\\{2kq+q^{2}\\}=\\{\gamma\\}$, we have that

$q\geq\sqrt{k^{2}+\\{\gamma\\}}-k\geq\frac{\\{\gamma\\}}{\sqrt{k^{2}+\\{\gamma\\}+k}}\geq\frac{\frac{1}{\Delta^{2}}}{\frac{4r|b|}{\Delta}}\geq\frac{1}{12r^{2}\Delta^{2}}\geq\frac{1}{48r^{4}}.$

Let us get a lower bound for $1-q.$ Again, assume that $\gamma\in\mathbb{Z}$.
Arguing analogously, we arrive at the bound

$2k(1-q)+(1-q)^{2}\geq\\{(k+1-q)^{2}\\}=\left\\{(k+1)^{2}-\frac{4\lambda^{2}b^{2}}{\Delta^{2}}-2q(1-q)\right\\}\geq\frac{1}{2}.$

Resolving the quadratic inequality with respect to $1-q$, we get:

$1-q\geq\sqrt{k^{2}+\frac{1}{2}}-k=\frac{\frac{1}{2}}{\sqrt{k^{2}+\frac{1}{2}}+k}\geq\frac{1}{\frac{8r|b|}{\Delta}}\geq\frac{1}{24r^{2}}.$

Now let $\gamma\notin\mathbb{Z}$. Let us consider the subcase where
$\\{\gamma\\}+2q(1-q)>1$. We get

$\left\\{(k+1)^{2}-\frac{4\lambda^{2}b^{2}}{\Delta^{2}}-2q(1-q)\right\\}\geq
1-\\{\gamma\\}\geq\frac{1}{\Delta^{2}}.$

Resolving the corresponding inequality with respect to $1-q$, we arrive at the
analogous lower bound $1-q\geq\frac{1}{48r^{4}}$.

Now we are to address the case where $\\{\gamma\\}+2q(1-q)<1$. Obviously

$\left\\{(k+1)^{2}-\frac{4\lambda^{2}b^{2}}{\Delta^{2}}-2q(1-q)\right\\}=1-\\{\gamma\\}-2q(1-q).$

For $1-q<\frac{1}{4\Delta^{2}}$ we have
$1-\\{\gamma\\}-2q(1-q)\geq\frac{1}{\Delta^{2}}-\frac{1}{2\Delta^{2}}=\frac{1}{2\Delta^{2}}.$
Arguing analogously, we obtain the following bound $1-q\geq\frac{1}{96r^{4}}$;
otherwise $1-q\geq\frac{1}{4\Delta^{2}}\geq\frac{1}{16r^{2}}$.

For $\\{\gamma\\}+2q(1-q)=1$ we have:

$1-q=\frac{1-\\{\gamma\\}}{2q}\geq\frac{1-\\{\gamma\\}}{2}\geq\frac{1}{2\Delta^{2}}\geq\frac{1}{8r^{2}}.$

Finally, we get the claimed bound $\min\\{q,1-q\\}\geq\frac{1}{96r^{4}}$.