# zbMATH — the first resource for mathematics

Efficient algorithms for the weighted $$k$$-center problem on a real line. (English) Zbl 1350.68259
Asano, Takao (ed.) et al., Algorithms and computation. 22nd international symposium, ISAAC 2011, Yokohama, Japan, December 5–8, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-25590-8/pbk). Lecture Notes in Computer Science 7074, 584-593 (2011).
Summary: We present $$O(\min\{n\log^{1.5} n, n\log n+k^2\log^2\frac{n}{k}\log^2 n\})$$ time algorithms for the weighted $$k$$-problem on a real line. Previously, the best known algorithms for this problem take $$O(n\log^{2} n)$$ time, or $$O(kn\log n)$$ time, or a time linear in $$n$$ but exponential in $$k$$. Our techniques involve developing efficient 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.
For the entire collection see [Zbl 1228.68006].

##### MSC:
 68U05 Computer graphics; computational geometry (digital and algorithmic aspects) 68P05 Data structures 68W40 Analysis of algorithms
Full Text: