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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Guarding Terrains with Guards on a Line

  • Byeonguk Kang,
  • Hwi Kim,
  • Hee-Kap Ahn

摘要

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.