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 gu…