Keywords

1 Introduction

Facility location represents an important class of practical problems from operations research, which can adequately be modeled by combinatorial optimization problems. A geometric modelling approach turns out to be successful for a variety of facility location problems where objects of interest, say, customers, roads, markets or inventories are geographically distributed. Under this approach an optimal placement of facilities (e.g of inventories, markets, petrol or charging stations) nearby objects of interest is to be found. Here objects of interest are modelled by simple geometric structures, which can be e.g. points, straight line segments or rectangles on the plane whereas locations of facilities are given by translates of simple objects like unit disks, axis-parallel squares or rectangles. In its simplest form optimization is done over placement of facilities to achieve the minimum total distance from the placed facilities to the objects of interest. Alternatively, it might be aimed at minimizing total number of the placed facilities while serving needs of all objects of interest.

This alternative type of problems is of the form of a simple to formulate problem from computational geometry: given a set \(\mathcal{{K}}\) of geometric objects on the plane, the smallest cardinality set \(\mathcal{{C}}\) of objects is to be found on the plane, chosen from a class \(\mathcal{{F}}\) of simply shaped objects, such that each object from \(\mathcal{{K}}\) is intersected by an object from \(\mathcal{{C}}\) in some prescribed way. In this paper, subquadratic time small constant factor approximation algorithms are designed for the following problem in which \(\mathcal{{F}}\) is a set of radius r disks and \(\mathcal{{K}}\) coincides with a finite set E of straight line segments on the plane.

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 proper edge crossings and a constant \(r>0,\) find the smallest cardinality set \(\mathcal{{C}}\) of disks of radius r such that \(e\,\cap \,\bigcup \limits _{C\in \mathcal{{C}}}C\ne \varnothing \) for each edge \(e\in E.\) Here each isolated vertex \(v\in V\) is treated as a zero-length segment \(e_v\in E.\) Moreover, the vertex set V is assumed to be in general position, i.e. no triple of points of V lies on any straight line.

Below the term “plane graph” is used to denote any straight line embedding of a planar graph whose (straight line) edges intersect at most at their endpoints.

The IPGD problem finds its applications in sensor network deployment and facility location. Suppose one needs to locate petrol or charging stations nearby all roads of a given road network. Geometrically, the network roads can be modeled by piecewise linear arcs on the plane. One can split these arcs into chains of elementary straight line segments such that any two of the resulting elementary segments intersect at most at their endpoints. To cover the road network with facility stations to some extent, it might be reasonable to place the minimum number of stations such that each piece of every road (represented by an elementary segment) is within a given distance from some of the placed stations. This modeling approach leads to a geometric combinatorial optimization model, which coincides with the IPGD problem.

The IPGD problem generalizes a classical NP-hard unit disk covering problem. In the unit disk covering problem one needs to cover a given finite point set E on the plane with the least cardinality set \(\mathcal{{C}}\) of unit disks. In the IPGD problem setting E generally contains non-zero length segments instead of points.

The IPGD problem has close connections with the classical geometric Hitting Set problem on the plane. To describe a Hitting Set formulation of the IPGD problem, some notation is given below. Suppose \(N_r(e)=\{x\in \mathbb {R}^2:d(x,e)\le r\},\) \(\mathcal{{N}}_r(E)=\{N_r(e):e\in E\}\) and d(x, e) is Euclidean distance between a point \(x\in {\mathbb {R}}^2\) and a segment \(e\in E;\) for a zero-length segment \(x\in \mathbb {R}^2\) \(N_r(x)\) denotes a radius r disk centered at x. Each object from \(\mathcal{{N}}_r(E)\) is a Euclidean r-neighborhood of some segment of E also called r-hippodrome or r-offset in the literature [2].

The IPGD problem can equivalently be formulated as follows: given a set \(\mathcal{{N}}_r(E)\) of r-hippodromes on the plane whose underlying straight line segments form an edge set of some plane graph \(G=(V,E),\) find the minimum cardinality point set C such that \(C\cap N\ne \varnothing \) for every \(N\in \mathcal{{N}}_r(E).\) In fact, C represents a set of centers of radius r disks, forming a solution to the IPGD problem. In the sequel, a set \(C_0\subset \mathbb {R}^2\) is called a piercing set for \(\mathcal{{N}}_r(E)\) when \(C_0\cap N\ne \varnothing \) for all \(N\in \mathcal{{N}}_r(E).\)

1.1 Related Work and Our Results

As far as we know, settings close to the IPGD problem are originally considered in [2]. Motivated by applications from sensor monitoring for urban road networks, they explore the case in which \(\mathcal{{F}}\) contains equal disks and E consists of n (generally properly overlapping) axis-parallel segments, giving 8-approximation \(O(n\log n)\)-time algorithm. Their algorithms can easily be extended to the case of sets E of straight line segments with bounded number of distinct orientations. A polynomial time approximation scheme (PTAS) is also proposed [10] for more general version of the IPGD problem in which disks of \(\mathcal{{C}}\) are chosen from some prescribed finite set \(\mathcal{{H}}\) of generally non-equal disks.

When pairs of segments of E are allowed to intersect properly and segments of E are admitted to have arbitrarily large number of distinct orientations, it is difficult to achieve a constant factor approximation at least by using known approaches. It is due to the non-constant lower bound obtained in [1] on integrality gap of a problem, which is close to the IPGD problem for \(r=0.\)

In [6] constant factor approximation algorithms are first proposed for the IPGD problem. Namely, a 100-approximate \(O(n^4\log n)\)-time algorithm is given for the problem in its general setting where E is formed by an edge set of an arbitrary plane graph. Moreover, due to applications, 68- and 54-approximate algorithms are given in [7] for special cases, where E is an edge set of a generalized outerplane graph and a Delaunay triangulation respectively as well as a 23-approximation algorithm is proposed under the assumption that all pairs of non-overlapping segments from E are at the distance more than r from each other.

Let us give some definitions. Let V be a finite point set in general position on the plane. Assuming that no 4 points of V lie on any circle, a plane graph \(G=(V,E)\) is called a Gabriel graph [9] when \([u,v]\in E\) iff intersection of V is empty with interior of the disk with diameter [u, v],  where [u, v] denotes a straight line segment with endpoints u and v. Under the same assumption a plane graph \(G=(V,E)\) is called a relative neighborhood graph [3] when \([u,v]\in E\) iff \(\max \{d(u,w), d(v,w)\}\ge d(u,v)\) for any \(w\in V\backslash \{u,v\}.\) Both types of plane graphs defined above appear in a variety of network applications. They represent convenient network topologies, simplifying routing and control in geographical (e.g. wireless) networks. They can also be applied when approximating complex networks.

In [8] faster \(O(n^2)\)-time 10-, 12- and 14-approximate algorithms are designed for the NP-hard ([5]) IPGD problem when E is being an edge set of a minimum Euclidean spanning tree, a relative neighborhood graph and a Gabriel graph respectively. This short paper extends this latter work by presenting much faster \(O\left( n^{3/2}\log ^2 n\right) \)-expected time 12- and 14- approximation algorithms for the IPGD problem for classes of relative neighborhood graphs and Gabriel graphs respectively. Obtained gain in time performance of the resulting approximation algorithms can be useful for facility location problems on large networks.

2 Basic Algorithm

The following algorithm lies at the core of our O(1)-approximation algorithms. It operates on two concepts whose definitions are given below.

Definition 1

A subset \(\mathcal{{I}}\subseteq \mathcal{{N}}_r(E)\) is called a maximal (with respect to inclusion) independent set in \(\mathcal{{N}}_r(E),\) if \(I\cap I'=\varnothing \) for any \(I,I'\in \mathcal{{I}},\) and for any \(N\in \mathcal{{N}}_r(E)\) there is some \(I\in \mathcal{{I}}\) with \(N\cap I\ne \varnothing .\)

Definition 2

Let \(G=(V,E)\) be a plane graph and \(f>0\) be some (r-independent) absolute constant. An edge \(e\in E\) is called f-coverable with respect to E,  if for any constant \(\rho >0\) one can construct at most f-point piercing set \(U(\rho ,e,E)\subset \mathbb {R}^2\) for \(\mathcal{{N}}_{\rho ,e}(E)=\{N\in \mathcal{{N}}_{\rho }(E):N\cap N_{\rho }(e)\ne \varnothing \}\) in polynomial time with respect to \(|\mathcal{{N}}_{\rho ,e}(E)|.\)

Let \(G=(V,E)\) be either a Gabriel or a relative neighborhood graph and \(r>0\) be a constant, forming an input of the IPGD problem. Work of our algorithm below can be split into two phases. During its first phase it performs a pass through E to iteratively grow its subset \(E'\) by adding segments from E into \(E'\) such that \(\mathcal{{N}}_r(E')\) finally becomes a maximal independent set in \(\mathcal{{N}}_r(E).\) Within this phase it applies a special (randomized) geometric data structure [4], implementing a Voronoi diagram for straight line segments of \(E',\) assuming Euclidean distance between segments. This data structure allows to

  1. 1.

    return a segment \(e'\in E'\) such that \(N_r(e)\,\cap \,N_r(e')\ne \varnothing \) for a given straight line segment \(e\in E\backslash E',\) or report that \(N_r(e)\cap N_r(e')=\varnothing \) for all \(e'\in E'\) in \(O(\log ^2|E'|)\) expected time;

  2. 2.

    insert new segments of \(E\backslash E'\) into \(E'\).

Then, during the second phase, another pass is performed over the built set \(E'\) to construct piercing sets for subsets of the form \(\mathcal{{N}}_{r,e}(E);\) each subset is defined by a segment \(e\in E'.\) Merging those piercing sets together into a point set \(C\subset \mathbb {R}^2,\) the algorithm yields a set \(\mathcal{{C}}=\{N_r(c):c\in C\}\) as an approximate solution to the IPGD problem instance, defined by G and r.

The algorithm implementation is based on a pseudo-code below. It contains a constant parameter \(f>0,\) which is specific to the class of plane graphs from which G is chosen. More precisely, \(f=12\) for the class of relative neighborhood graphs and \(f=14\) for the class of Gabriel graphs.

figure a

At the basic algorithm step 7 within its second phase, to implement an auxiliary procedure of seeking a piercing set \(U(e')\) for \(\mathcal{{N}}_r(E_{e'}),\) two special procedures are used, which are designed in [8]. Their performance is reported in two lemmas below (see lemmas 1 and 5 as well as implementations of those procedures in [8]).

Lemma 1

Any edge \(e\in E\) is 12-coverable of an arbitrary subgraph \(G=(V,E)\) of a relative neighborhood graph. More precisely, for any \(\rho >0\) the respective piercing set \(U(\rho ,e,E)\) for \(\mathcal{{N}}_{\rho ,e}(E)\) can be found in O(1) time.

Lemma 2

Any edge \(e\in E\) is 14-coverable of an arbitrary subgraph \(G=(V,E)\) of a Gabriel graph. Namely, for any \(\rho >0\) the respective piercing set \(U(\rho ,e,E)\) for \(\mathcal{{N}}_{\rho ,e}(E)\) can be found in O(1) time.

In [8] an analogous algorithm (to the basic algorithm above) is described, working in \(O(n\mathrm{{OPT}})\) time, where \(\mathrm{{OPT}}\) is the problem optimum. Namely, it does \(O(\mathrm{{OPT}})\) “heavy” steps such that each step performs a single pass through a subset of E,  which can be \(\Omega (n)\)-sized, thus, taking O(n) time. In distinction to this latter algorithm, work of our algorithm is organized in the different way. It avoids doing those \(O(\mathrm{{OPT}})\) “heavy” steps and performs O(n) “lighter” steps instead at its first phase, each of which mostly consists in querying and updating a nearest neighbor data structure, built on the \(O(\mathrm{{OPT}})\)-sized subset of E. Its expected query times are polylogarithmic with respect to \(\mathrm{{OPT}}.\)

3 Our Results

Applying our basic algorithm and O(1)-time auxiliary procedures from [8] at its step 7, which are titled Partial r -disk cover search for 2 r -hippodromes on RNG edges and Partial r-disk cover search for 2 r -hippodromes on GG edges, the following results can be obtained.

Theorem 1

There is an \(O\left( n^{3/2}\log ^2 \mathrm{{OPT}}\right) \)-expected time f-approximate algorithm for the IPGD problem in the graph class \(\mathcal{{G}},\) where

  1. 1.

    \(f=12\) and \(\mathcal{{G}}\) is the class of subgraphs of relative neighborhood graphs;

  2. 2.

    \(f=14\) and \(\mathcal{{G}}\) is the class of subgraphs of Gabriel graphs.