Carleton University - School of Computer Science Honours Project
Winter 2019
Optimization Problems for Points in Disks
Zachary Fry
SCS Honours Project Image
ABSTRACT
We propose algorithms to solve problems related to client-server coverage in several limited 2D planes. These algorithms are based on one developed in the paper "Faster Algorithms for some Optimization Problems on Collinear Points" by Biniaz et al. (Reference in Paper) The input to client-server coverage is 2 sets of points, called clients and servers. There are n clients and m servers. The goal will be to place disks such that all the clients are covered by at least one disk and each disk is centred on a server. We call the solution optimal when the sum of the radii is minimized. What will change in each of the scenarios will be the arrangement of the points. These arrangements are as follows: 1. Points are on a line: We propose a modification to the algorithm by Biniaz et al. [2] While their algorithm always runs in O((n + m)^2 ), ours runs in at most O((m + n)^2 ) but under certain circumstances can run faster, to a minimum of O(m + n). 2. All points are located on the boundary of a circle: We propose a modification to the algorithm by Biniaz et al. so that it can solve the problem when all the points are located on the boundary of a circle with radius R. This algorithm will run in O((m + n)^3 ).