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].

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
68P05 Data structures
68W40 Analysis of algorithms
PDF BibTeX Cite
Full Text: DOI