For a terrain with n vertices, the paper gives an O(k^2 lambda_{k-1}(n) log n)-time algorithm for placing k guards on a lowest line above the terrain (even k), an analogous O(k^2 lambda_{k-2}(n) log n) bound for odd k, and O(kn) time for a partition-based variant.
On the planar two-watchtower problem
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
fields
cs.CG 1years
2025 1verdicts
CONDITIONAL 1representative citing papers
citing papers explorer
-
Guarding Terrains with Guards on a Line
For a terrain with n vertices, the paper gives an O(k^2 lambda_{k-1}(n) log n)-time algorithm for placing k guards on a lowest line above the terrain (even k), an analogous O(k^2 lambda_{k-2}(n) log n) bound for odd k, and O(kn) time for a partition-based variant.