Constant Factor Approximation for Intersecting Line Segments with Disks

Abstract

Fast constant factor approximation algorithms are devised for a problem of intersecting a set of n 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. Exploiting its tough connection with the geometric Hitting Set problem we give $(100+\varepsilon )$-approximate $O(n^4\log n)$-time and $O(n^2\log n)$-space algorithm based on the modified Agarwal-Pan reweighting algorithm, where $\varepsilon >0$ is an arbitrary small constant. Moreover, $O(n^2\log n)$-time and $O(n^2)$-space 18-approximation is designed for the case where G is any subgraph of a Gabriel graph.

This work was supported by Russian Science Foundation, project 14-11-00109.

1 Introduction

Design of fast algorithms with low approximation factors is an important task for many NP-hard geometric combinatorial optimization problems among which are numerous special settings of the known geometric Hitting Set problem on the plane which itself has close links to optimal geometric coverage and piercing problems. The classical Hitting Set problem is to find the smallest cardinality subset H of some given set $Y\subseteq \mathbb {R}^2$ such that $H\cap R\ne \varnothing$ for any $R\in {\mathcal {R}},$¹ where ${\mathcal {R}}$ is some given family of subsets of $\mathbb {R}^2$ also called objects in the sequel. Moreover, a pair $(Y,{\mathcal {R}})$ is associated with each instance of the Hitting Set problem called a range space. In this paper fast constant factor approximation algorithms are constructed for special settings of the geometric Hitting Set problem related to network analysis.

Intersecting Plane Graph with Disks (IPGD): given a straight line drawing (or a plane graph) $G=(V,E)$ of an arbitrary simple 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 below in our paper to denote the problem for simplicity of presentation.

The IPGD problem could be of interest in network security, sensor network deployment and facility location. For example, in [8] its sensor deployment applications are reported for road networks. Namely, for a road network possible intrusion activity must be monitored by deploying sensor devices near its roads which have uniform circular sensing area. As full network surveillance might be costly, it may be sufficient to guarantee that the intruder movement is detected at least once somewhere along any its road. Minimizing total cost of the deployed identical sensors can be modeled in the form of the IPGD problem assuming that network roads are modeled by interior disjoint straight line segments. Moreover, another network security application may be of interest of the IPGD problem for optical fiber networks following the approach of [1].

As far as it is known, special settings are first considered close to the IPGD problem in [8] for cases of (possibly overlapping) axis-parallel and bounded length straight line segments. Of course, the general IPGD problem can be considered as the special geometric intersection problem which is to find the smallest cardinality subset of radius r disks whose union has nonempty intersection with each segment from E. Besides, it coincides with the Hitting Set problem in which $Y=\mathbb {R}^2,$ ${\mathcal {R}}={\mathcal {N}}_r(E)=\{\{x\in \mathbb {R}^2:d(x,e)\le r\}:e\in E\}$ and d(x, e) is Euclidean distance between a point $x\in {\mathbb {R}}^2$ and a segment $e\in E.$

Moreover, the IPGD problem generalizes a classical NP-hard disk covering problem on the case of non-zero length segments. In the latter problem one needs to cover a given finite point set on the plane with the smallest cardinality set of equal disks. Generally, the IPGD problem is quite different from the Hitting Set problem for families of identical disks (which is equivalent to the disk covering problem) and other bounded aspect ratio objects as segment lengths are not assumed to be bounded from above by any linear function of r. Surprisingly, it admits fast constant factor approximation algorithms whose factors are modest.

In the recent years a significant reduction is achieved in complexity of those approximation algorithms for several geometric Hitting Set problems which use ideas of local search [3, 7]. Local search is initially used to design PTAS [11] for geometric Hitting Set problems. More precisely, local search approach has become quite competitive for designing low constant factor approximations for geometric Hitting Set problems for families of disks [7] and pseudo-disks² [3]. As straight line segments from E intersect at most at their endpoints, objects from ${\mathcal {N}}_r(E)$ form a family of pseudo-disks without loss of generality³. Therefore an algorithm from [3] yields 4-approximate solution for the IPGD problem in $O(n^{18})$-time, being too complicated, where $n=|E|.$

In this paper another approach is taken which involves using epsilon nets [2]. It gives faster algorithms at the expense of larger constants in their approximation factors. More precisely, $\left( 50+52\sqrt{\frac{12}{13}}+\varepsilon \right)$-approximation algorithm is proposed for the IPGD problem working in $O\left( n^4\log n\right)$ time, where $\varepsilon >0$ is an arbitrary small constant. Moreover, an $O(n^2\log n)$-time 18-approximation is designed for the case where G is any subgraph of a Gabriel graph. Within epsilon net approach the only relevant constant factor approximation is known for the Hitting Set problem for sets of pseudo-disks [12] with similar time complexity bounds, giving huge constant approximation factors. Thus, our algorithms give a competitive tradeoff of approximation factor and time complexity being compared with known local search and epsilon net based approximation algorithms designed for similar geometric Hitting Set problems on sets of pseudo-disks.

There are a few restricted settings of the IPGD problem for which low constant factor approximation algorithms are designed of small complexity. If E contains only zero length segments, a 4-approximation is known [4] which works in $O(n\log n)$ time and O(n) space. Moreover, when E consists of axis-parallel segments, 8-approximation algorithm is given [8] taking $O(n\log n)$ time and $O(n\log n)$ space.

2 Constant Factor Approximation for the IPGD Problem

2.1 Algorithmic Ideas: Epsilon Nets and Independent Sets

As reported in the Introduction, the IPGD problem is equivalent for a set E of straight line segments to the Hitting Set problem on a set ${\mathcal {N}}_r(E)$ of Euclidean r-neighbourhoods of segments of E (which are often called hippodromes). To get constant factor approximation algorithms for the IPGD problem improved versions of two approaches are used from [2, 12], which are devised for the general geometric Hitting Set problem.

To outline basic concepts behind our algorithms for the IPGD problem, we start with the following idea which underlies low constant factor approximation algorithms for cases of the IPGD problem with either zero-length [4] or axis-parallel [8] segments. Say, if segments from E are all of zero-length, the idea is to apply a “divide-and-conquer” approach by finding a maximal (with respect to inclusion) independent set ${\mathcal {I}}$ of radius r disks within ${\mathcal {N}}_r(E),$ i.e. a maximal subset of pairwise non-intersecting disks. As 7 radius r disks are sufficient to cover 2r radius disk, 7-point set $S_I$ can be constructed such that $S_I\cap M\ne \varnothing$ for any $M\in {\mathcal {N}}_I=\{N\in {\mathcal {N}}_r(E):N\cap I\ne \varnothing \}$ and $I\in {\mathcal {I}}.$ Therefore a set $\bigcup \limits _{I\in {\mathcal {I}}}S_I$ gives a 7-approximate solution.

In our paper a similar but more relaxed and indirect approach is employed which is inspired by work [12]. This is because the aforementioned idea can not be applied to the general IPGD problem more or less directly. Indeed, its application amounts to finding constant cardinality hitting sets for sets ${\mathcal {M}}_I$ of objects, being subsets of ${\mathcal {N}}_I,$ associated with some object $I\in {\mathcal {N}}_r(E).$ But there can be no such hitting sets for ${\mathcal {M}}_I$ that have their sizes uniformly (within ${\mathcal {I}})$ bounded from above by any absolute constant. This is because, first, $I=\{x\in \mathbb {R}^2:d(x,e(I))\le r\}$ for some straight line segment $e(I)\in E$ whose Euclidean length is not assumed to be bounded from above by any linear function of r. Second, the number of distinct orientations of segments from E can be arbitrarily large. Therefore, it is not possible to partition segments of E into constant number of groups of segments with similar orientations and apply the aforementioned idea in each group as done in [8].

Instead, one can generalize object independency notion by allowing intersection of objects in maximal independent set, but control amount of their overlapping in some way. Following approach of [2], one can get an approximate solution to the IPGD problem by a compound algorithm which combines two different subalgorithms, first of which exercises a similar “divide-and-conquer” scheme, seeking those generalized independent sets and respective partitioning of the family ${\mathcal {N}}_r(E).$

First Subalgorithm. Let $0<\varepsilon <1.$ Assuming that a positive weight map $w:Y_0\rightarrow \mathbb {R}_+$ is defined on some finite point set $Y_0\subset \mathbb {R}^2$ with $\mathrm{{OPT}}=\mathrm{{OPT}}(\mathbb {R}^2,{\mathcal {N}}_r(E))= \mathrm{{OPT}}(Y_0,{\mathcal {N}}_r(E))$,⁴ first subalgorithm returns a hitting set for a subset of those objects from ${\mathcal {N}}_r(E)$ whose weight is at least $\varepsilon$th fraction of $w(Y_0),$ where $w(N)=\sum \limits _{y\in N\cap Y_0}w(y)$ for $N\subseteq \mathbb {R}^2$ and $\mathrm{{OPT}}(Y,{\mathcal {R}})$ is the optimum of the Hitting Set problem for a given range space $(Y,{\mathcal {R}}).$ Hitting set has a special name of the kind, which is output by the first subalgorithm.

Definition 1

Let $0<\varepsilon <1$ and $w:Y_0\rightarrow \mathbb {R}_+.$ A subset $Y'\subset \mathbb {R}^2$ is called a (weighted) weak $\varepsilon$-net [9] for a range space $(Y_0,{\mathcal {N}}_r(E),w)$ if $Y'\cap N\ne \varnothing$ for any $N\in {\mathcal {N}}_r(E)$ with $w(N)>\varepsilon w(Y_0).$

To build a weak $\varepsilon$-net for space $(Y_0,{\mathcal {N}}_r(E),w),$ first subalgorithm initially seeks a maximal subset ${\mathcal {I}}$ of almost non-intersecting objects within the subset ${\mathcal {N}}_{\varepsilon }=\{N\in {\mathcal {N}}_r(E):w(N)>\varepsilon w(Y_0)\}.$ To control amount of overlap of objects from ${\mathcal {I}}$ special parameter $\delta$ and a weight map w on $Y_0$ are used as follows [12].

Definition 2

Given a subset ${\mathcal {P}}\subseteq {\mathcal {N}}_r(E),$ a parameter $\delta >0$ and a weight map $w:Y_0\rightarrow \mathbb {R}_+,$ a subset ${\mathcal {I}}={\mathcal {I}}(\delta )\subseteq {\mathcal {P}}$ is called a maximal (with respect to inclusion) $\delta$-independent for a range space $(Y_0,{\mathcal {P}},w)$ if

$$w(I\cap I')\le \delta w(Y_0)$$

for any distinct $I,I'\in {\mathcal {I}}$ and for any $N\in {\mathcal {P}}$ there is some $I=I(N)\in {\mathcal {I}}$ with $w(N\cap I)>\delta w(Y_0).$

Below a pseudo-code is presented of the first subalgorithm. It involves using an auxiliary procedure to seek hitting sets $H_I(\delta )$ of size at most $\frac{c_1}{\delta }+c_2$ for subsets ${\mathcal {N}}_{I}(\delta )\subseteq \{N\in {\mathcal {N}}_r(E):w(N\cap I)>\delta w(I)\}$ for a given $I\in {\mathcal {N}}_r(E)$ and a parameter $0<\delta <1,$ where $c_1$ and $c_2$ are some constants. Such a procedure is named a hitting set finder below whereas sets ${\mathcal {N}}_{I}(\delta )$ are referred to as sets of dependent objects. It is assumed to exist (see the Lemma 2 below).

Bounds for Size of Epsilon Nets, Given by the First Subalgorithm. The following lemma summarizes on the length of the weak $\varepsilon$-net $H_{\theta _0}$ returned by the first subalgorithm and provides a way to choose its parameters $\alpha ,\beta ,\tau$ and $\theta _0$ to guarantee $O\left( \frac{1}{\varepsilon }\right)$ bounds for $|H_{\theta _0}|.$ It inherits main ideas of work [12] but establishes better upper bounds for $|H_{\theta _0}|$ by at least factor of 2.

Lemma 1

Suppose there are absolute constants $\alpha ,\beta ,\tau$ and a graph $G_{{\mathcal {I}}}=({\mathcal {I}},U)$ for any ${\mathcal {I}}\subseteq {\mathcal {N}}_r(E)$ such that $|U|\le \beta |{\mathcal {I}}|$ and $m_{{\mathcal {I}}}(y)\ge \alpha n_{{\mathcal {I}}}(y)-\tau$ for every $y\in Y_0,$ where $n_{{\mathcal {I}}}(y)=|\{I\in {\mathcal {I}}:y\in I\}|$ and $m_{{\mathcal {I}}}(y)=|\{\{I,I'\}\in U:y\in I\cap I'\}|.$ Then a weak $\varepsilon$-net $H_{\theta _0}$ can be constructed for a range space $(Y_0,{\mathcal {N}}_r(E),w)$ by the first subalgorithm for any $0<\varepsilon <1$ of size at most

$$|H_{\theta _0}|\le \left[ \left( 1+\frac{1}{\sqrt{1+\frac{c_2\alpha }{c_1\beta }}}\right) \left( \frac{2c_1\tau \beta }{\alpha ^2}+\frac{c_2\tau }{\alpha }\right) +\frac{c_2\tau }{\alpha \sqrt{1+\frac{c_2\alpha }{c_1\beta }}}\right] \frac{1}{\varepsilon },$$

where $\theta _0=\frac{\frac{\alpha }{\beta }}{1+\sqrt{1+\frac{c_2\alpha }{c_1\beta }}}.$

Definition 3

A map is called a structural map for the range space $(Y_0,{\mathcal {N}}_r(E)),$ which assigns a graph $G_{\mathcal {I}}$ for each ${\mathcal {I}}\subseteq {\mathcal {N}}_r(E)$ as defined in the Lemma 1, where the constants $\alpha ,\beta$ and $\tau$ are named as structural parameters for that space.

Second Subalgorithm. Second subalgorithm adjusts the parameter $\varepsilon$ and computes a weight map w to get $|H_{\theta _0}|=O(\mathrm{{OPT}}).$ Namely, it computes point weights $w(y),\,y\in Y_0,$ to get the inequality

$$\begin{aligned} w(N)>\varepsilon w(Y_0) \end{aligned}$$

(1)

hold for all $N\in {\mathcal {N}}_r(E),$ where $\varepsilon$ is also found such that $\varepsilon =\frac{1}{\lambda _0\mathrm{{OPT}}}$ for some $\lambda _0\approx 1.$ To get a suitable weight map (i.e. satisfying the inequality (1) for all $N\in {\mathcal {N}}_r(E))$ and compute right $\varepsilon$ a modification of the known fast Agarwal-Pan algorithm [2] is applied which is similar to the one in [6].

Main Algorithm. Finally, the compound main algorithm works as follows: second subalgorithm runs to compute a suitable weight map $w_0$ and gets a value $\varepsilon _0=\frac{1}{{\lambda _0\mathrm {OPT}}}$ of the parameter $\varepsilon$ whereas first (weak epsilon net seeking) subalgorithm constructs a hitting set for ${\mathcal {N}}_r(E)$ being applied for found $\varepsilon _0$ and $w_0,$ thus, arriving at the constant factor approximation due to the Lemma 1. Namely, a constant C in the bound $|H_{\theta _0}|\le \frac{C}{\varepsilon }$ (see the Lemma 1) provides an upper bound on the approximation factor of the compound algorithm.

2.2 Geometric Constructions

Hitting Set Finders for Sets of Dependent Objects. In order for the first subalgorithm to be working, a special procedure should be designed which returns hitting sets $H_I(\delta )$ of length at most $\frac{c_1}{\delta }+c_2$ for sets ${\mathcal {N}}_{I}(\delta )\subseteq \{N\in {\mathcal {N}}_r(E):w(N\cap I)>\delta w(I)\}\cup \{I\},$ where $I\in {\mathcal {N}}_r(E),$ $0<\delta <1$ and $c_1,c_2>0$ are some absolute constants. Such a special procedure is described below.

Some notations are first given to simplify our work with machinery of straight line segments and their Euclidean r-neighbourhoods. Let $N_r(e)=\{x\in \mathbb {R}^2:d(x,e)\le r\}$ for a straight line segment e on the plane; particularly, for $x\in \mathbb {R}^2$ $N_r(x)$ denotes a radius r disk centered at x. Moreover, for $N\in {\mathcal {N}}_r(E)$ a segment e(N) is such that $N=N_r(e(N))$ whereas $E({\mathcal {N}})\subseteq E$ is the segment set with ${\mathcal {N}}={\mathcal {N}}_r(E({\mathcal {N}})).$ Set $z_e(e')=\{x\in e':d(x,e)\le 2r\}$ and let l(e) be a straight line through a non-zero length segment e,  $h_1(e)$ and $h_2(e)$ be positive and negative halfplanes respectively, whose boundary coincides with l(e);  here orientation is chosen arbitrarily for l(e). The set $\mathrm{{bd}}\,N_r(e)$ can be represented in the form of a union of two halfcircles and two segments $f_1(e)$ and $f_2(e),$ where $f_i(e)\subset \mathrm{{int}}\,h_i(e),\,i=1,2.$ Let $l_i(e)$ be the straight line through $f_i(e).$

The procedure below seeks hitting sets for sets of dependent objects in the case of interior disjoint segments. It is based on finding hitting sets for sets of 1-dimensional r-neighbourhoods of (interval) projections of segments $\{z_e(e')\}_{e'\in E'},\,E'\subseteq E,$ onto straight lines $l_i(e).$ Let $N_{ir}(f)=\{x\in l_i(e):d(x,f)\le r\}$ for an arbitrary interval $f\subset l_i(e),\,i=1,2.$

The following lemma summarizes on the procedure performance.

Lemma 2

Let $n=|{\mathcal {N}}_I(\delta )|.$ The Hitting Set Finder for Dependent Objects procedure returns a hitting set $H_I(\delta )$ for ${\mathcal {N}}_I(\delta )$ of size at most $\frac{8}{\delta }+2$ in $O(n\log n)$ time and O(n) space.

Structural Map for the IPGD Problem. According to the Lemma 1, to guarantee $O\left( \frac{1}{\varepsilon }\right)$ bounds for size of weak epsilon nets, obtained from the first subalgorithm, a structural map should be identified for $(Y_0,{\mathcal {N}}_r(E)).$ In other words, one needs to build a structural map by assigning a graph for each subset ${\mathcal {N}}\subseteq {\mathcal {N}}_r(E)$ or, equivalently, for each subset $E'\subseteq E.$ It can be established that Delaunay triangulation (planar) graph [5] of the segment set $E'$ turns out to be the sought graph for which ratios $\frac{\beta }{\alpha }$ and $\frac{\tau }{\alpha }$ are small.

Lemma 3

There is a structural map for $(Y_0,{\mathcal {N}}_r(E))$ with $\beta =3$ and $\alpha =\tau =1.$

2.3 Performances of Our Approximation Algorithms

Our main result is on constant factor approximation for the IPGD problem.

Theorem 1

Let $n=|E|.$ There is a $\left( 50+52\sqrt{\frac{12}{13}}+\nu \right)$-approximation for the IPGD problem, which works in

$$O\left( \left( n^2+\frac{n\log n}{\nu ^2}+\frac{\log n}{\nu ^3}\right) n^2\log n\right) $$

time and $O\left( \frac{n^2\log n}{\nu }\right)$ space for any small $\nu >0.$

Let S be a plane point set in general position no 4 of which are cocircular.

Definition 4

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.

In [10] it is shown that the IPGD problem is NP-hard for the case where E is edge set of a Gabriel graph. The theorem below reports an approximation algorithm to exist for sets of segments given by edge sets of Gabriel graphs.

Theorem 2

If G is subgraph of a Gabriel graph, there is a 18-approximation algorithm, which works in $O(n^2\log n)$ time and $O(n^2)$ space.

3 Conclusion

Approximation algorithms with constant factors are proposed for a problem of intersecting a set of n straight line segments, overlapping at most at their endpoints, with the least cardinality set of equal disks. Namely, a $(100+\varepsilon )$-approximation is given which works in $O(n^4\log n)$ time and $O(n^2\log n)$ space. Also 18-approximation is reported to exist with $O(n^2\log n)$ time and $O(n^2)$ space complexities for the case where segments form edge set of a Gabriel graph.