2013/01/31 by Danny Z. Chen, Jian Li, Chen, Danny Z. +3
Business, Management and Accounting · Computer Science · #Computational Geometry and Mesh Generation #Facility Location and Emergency Management #Optimization and Search Problems #cs.CG #cs.DS
paper · pdf · doi:10.48550/arxiv.1301.7512
13 pages, 3 figures. Thanks to Amir Tamir, discussions on previous work are updated in this version
arxiv created 2014/03/06 · arxiv updated 2014/03/07
We consider the problem of finding k centers for n weighted points on a real line. This (weighted) k-center problem was solved in O(n log n) time previously by using Cole's parametric search and other complicated approaches. In this paper, we present an easier O(n log n) time algorithm that avoids the parametric search, and in certain special cases our algorithm solves the problem in O(n) time. In addition, our techniques involve developing interesting data structures for processing queries that find a lowest point in the common intersection of a certain subset of half-planes. This subproblem is interesting in its own right and our solution for it may find other applications as well.