Biniaz, Ahmad ;
Bose, Prosenjit ;
Carmi, Paz ;
Maheshwari, Anil ;
Munro, Ian ;
Smid, Michiel
Faster Algorithms for some Optimization Problems on Collinear Points
Abstract
We propose faster algorithms for the following three optimization problems on n collinear points, i.e., points in dimension one. The first two problems are known to be NPhard in higher dimensions.
1) Maximizing total area of disjoint disks: In this problem the goal is to maximize the total area of nonoverlapping disks centered at the points. Acharyya, De, and Nandy (2017) presented an O(n^2)time algorithm for this problem. We present an optimal Theta(n)time algorithm.
2) Minimizing sum of the radii of clientserver coverage: The n points are partitioned into two sets, namely clients and servers. The goal is to minimize the sum of the radii of disks centered at servers such that every client is in some disk, i.e., in the coverage range of some server. LevTov and Peleg (2005) presented an O(n^3)time algorithm for this problem. We present an O(n^2)time algorithm, thereby improving the running time by a factor of Theta(n).
3) Minimizing total area of pointinterval coverage: The n input points belong to an interval I. The goal is to find a set of disks of minimum total area, covering I, such that every disk contains at least one input point. We present an algorithm that solves this problem in O(n^2) time.
BibTeX  Entry
@InProceedings{biniaz_et_al:LIPIcs:2018:8721,
author = {Ahmad Biniaz and Prosenjit Bose and Paz Carmi and Anil Maheshwari and Ian Munro and Michiel Smid},
title = {{Faster Algorithms for some Optimization Problems on Collinear Points}},
booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)},
pages = {8:18:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770668},
ISSN = {18688969},
year = {2018},
volume = {99},
editor = {Bettina Speckmann and Csaba D. T{\'o}th},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8721},
URN = {urn:nbn:de:0030drops87219},
doi = {10.4230/LIPIcs.SoCG.2018.8},
annote = {Keywords: collinear points, range assignment}
}
2018
Keywords: 

collinear points, range assignment 
Seminar: 

34th International Symposium on Computational Geometry (SoCG 2018)

Issue date: 

2018 
Date of publication: 

2018 