Guarding Terrains with Guards on a Line
摘要
Given an x-monotone polygonal chain T with n vertices, and an integer k, we consider the problem of finding the lowest horizontal line L lying above T with k point guards lying on L, so that every point on the chain is visible from some guard. A natural optimization is to minimize the y-coordinate of L. We present an algorithm for finding the optimal placements of L and k point guards for T in \(O(k^2\lambda _{k-1}(n)\log n)\) time for even numbers \(k\ge 2\) , and in \(O(k^2\lambda _{k-2}(n)\log n)\) time for odd numbers \(k \ge 3\) , where \(\lambda _{s}(n)\) is the length of the longest (n, s)-Davenport-Schinzel sequence. We also study a variant with an additional requirement that T is partitioned into k subchains, each subchain is paired with exactly one guard, and every point on a subchain is visible from its paired guard. When L is fixed, we can place the minimum number of guards in O(n) time. When the number k of guards is fixed, we can find an optimal placement of L with k point guards lying on L in O(kn) time.