Efficient algorithms for the one-dimensional k-center problem

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.

Authors

• Danny Z. Chen University of Notre Dame
• Jian Li
• Haitao Wang School of Computer Science and Engineering, Sun Yat-sen University, Guangzhou, China

Keywords

• k-center
• One-dimension
• Facility locations
• Algorithms
• Data structures
• 2-D sublist LP queries
• Computational geometry