The shortest watchtower and related problems for polyhedral terrains
Micha Sharir · Information Processing Letters · 1988
We present an O(n log2 n) algorithm for finding the shortest vertical segment (‘watchtower’) uv that has to be erected on a polyhedral terrain S with n faces, so that its top endpoint can see the entire terrain S. An extension of our technique yields an O(n log2 n + k) time algorithm for calculating the lower envelope of two polyhedral terrains, one of which is convex, where k is combinatorial complexity of the output envelope.