Abstract | ||
---|---|---|
We consider the $k$-center problem in which the centers are constrained to lie on two lines. Given a set of $n$ weighted points in the plane, we want to locate up to $k$ centers on two parallel lines. We present an $O(n\log^2 n)$ time algorithm, which minimizes the weighted distance from any point to a center. We then consider the unweighted case, where the centers are constrained to be on two perpendicular lines. Our algorithms run in $O(n\log^2 n)$ time also in this case. |
Year | Venue | Field |
---|---|---|
2015 | CoRR | Binary logarithm,Perpendicular,Combinatorics,Radius,Mathematics |
DocType | Volume | Citations |
Journal | abs/1512.07533 | 0 |
PageRank | References | Authors |
0.34 | 9 | 7 |
Name | Order | Citations | PageRank |
---|---|---|---|
Binay Bhattacharya | 1 | 96 | 12.42 |
Sandip Das | 2 | 256 | 48.78 |
Yuya Higashikawa | 3 | 64 | 12.71 |
Tsunehiko Kameda | 4 | 282 | 35.33 |
naoki katoh | 5 | 1101 | 187.43 |
Hirotaka Ono | 6 | 400 | 56.98 |
Yota Otachi | 7 | 161 | 37.16 |