2025/05/05 by Byeonguk Kang, Kang, Byeonguk, Hwi Kim +3
Engineering · #Computational Geometry (cs.CG) #FOS: Computer and information sciences #Soil Mechanics and Vehicle Dynamics #Tree Root and Stability Studies
paper · pdf · doi:10.48550/arxiv.2505.02373
openalex publication_date 2025/05/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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(k2λk-1(n)log n) time for even numbers k≥ 2, and in O(k2λk-2(n)log n) time for odd numbers k ≥ 3, where λ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.