Efficient algorithms for selected constrained center location problems

Facility location problems are an essential family of problems in combinatorial optimization and computational geometry which has many applications in other fields of computer science like computer networks, robotics, etc. In this thesis, we study two classes of facility location problems. In the first part, we study the effect of a beacon/repulsor in a polygonal region and in the second part, we study the proximity connected k-center problem (PCkCP). Beacons and repulsors are two types of actuators that appear in many applications such as sensor networks and robot motion planning. A beacon (resp. repulsor) in a polygonal region P is an object that can attract (resp. repel) point particles in P. We say a beacon b ∈ P attracts a point p ∈ P if the particle initially located at p finally gets to b under its attraction influence. b is called a beacon kernel point of P if it attracts any point in P. Similarly, for three points r, p, t ∈ P, we say a repulsor at r sends p to t if the particle initially located at p finally gets to t under the repulsion influence. In our first result, we consider the discrete beacon kernel problem (DBKP) in simple polygons and provide a sub-quadratic time algorithm to solve it. In the DBKP, we are given a set of points X ⊆ P and the objective is specifying the beacon kernel points in X . Also, we show how our method can be extended to the case where we replace X by a set of line segments inside P. In our second result, we consider the particle transmitting problem. In this problem, the objective is determining the points in the given polygonal domain that can be sent to a given target point by activating only one repulsor. We propose an efficient polynomial time algorithm for this problem. Next, we define the proximity connectedness condition (PCC) for a set C of centers in a metric space. We say C satisfies the PCC if each pair of centers can communicate with each other via the other centers assuming any two centers sufficiently close to each other can directly communicate. In the PCkCP, we are given a set of demand points in a metric space and a positive integer k. The objective is locating k centers as close as possible to the demand points while satisfying the PCC. As our third result, we study the PCkCP when the underlying space is a path and provide a sub-quadratic time algorithm for the problem. Finally, we consider the proximity connected 2-center problem in the plane and propose an efficient polynomial time algorithm for it.