Computing the shortest watchtower of a polyhedral terrain in O(nlogn) time

Chazelle, 1989, Lines in space—combinatorics, algorithms and applications, 382 Chazelle, 1986, Fractional cascading, Part I: A data structuring technique, Algorithmica, 1, 133, 10.1007/BF01840440 Cole, 1986, Searching and sorting similar lists, J. Algorithms, 7, 202, 10.1016/0196-6774(86)90004-0 Cole, 1989, Visibility problems for polyhedral terrains, J. Symb. Comput., 7, 11, 10.1016/S0747-7171(89)80003-3 Chazelle, 1990, An algorithm for generalized point location and its application, J. Symb. Comput., 10, 281, 10.1016/S0747-7171(08)80065-X deFloriani, 1986, A visibility-based model for terrain features, 235 Dobkin, 1985, A linear time algorithm for determining the separation of convex polyhedra, J. Algorithms, 6, 381, 10.1016/0196-6774(85)90007-0 Dobkin, 1990, Determining the separation of preprocessed polyhedra—a unified approach, 400 Kirkpatrick, 1983, Optimal search in planar subdivisions, SIAM J. Comput., 12, 28, 10.1137/0212002 Muller, 1979, Finding the intersection of n half-spaces in time O(nlogn), Theoret. Comput. Sci., 8, 45 Preparata, 1992, A simplified technique for hidden-line elimination in terrains, 577, 135 Rockafellar, 1970 Reif, 1988, An efficient output-sensitive hidden-surface removal algorithms and its parallelization, 193 Sharir, 1988, The shortest watchtower and related problems for polyhedral terrains, Inform. Process. Lett., 29, 265, 10.1016/0020-0190(88)90120-2 Sarnak, 1986, Planar point location using persistent search trees, Comm. ACM, 29, 669, 10.1145/6138.6151