Skip to main content

Efficient algorithms for selected constrained center location problems

Resource type
Thesis type
(Thesis) Ph.D.
Date created
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.
109 pages.
Copyright statement
Copyright is held by the author(s).
This thesis may be printed or downloaded for non-commercial research and scholarly purposes.
Supervisor or Senior Supervisor
Thesis advisor: C., Shermer, Thomas
Thesis advisor: Bhattacharya, Binay
Member of collection
Download file Size
etd22317.pdf 5.92 MB

Views & downloads - as of June 2023

Views: 33
Downloads: 1