Computing the shortest watchtower of a polyhedral terrain in \(O(n\log n)\) time.

DOI10.1016/S0925-7721(96)00009-0zbMath1133.68467OpenAlexW2074915405MaRDI QIDQ2482906

Binhai Zhu

Publication date: 25 April 2008

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0925-7721(96)00009-0

Mathematics Subject Classification ID

Computational aspects related to convexity (52B55) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items (7)

Routing in a polygonal terrain with the shortest beacon watchtower ⋮ Parametric search: three new applications ⋮ Inapproximability of finding maximum hidden sets on polygons and terrains ⋮ Guarding a terrain by two watchtowers ⋮ Three-dimensional weak visibility: Complexity and applications ⋮ Acrophobic guard watchtower problem ⋮ Approximation algorithms for terrain guarding.

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fractional cascading. I: A data structuring technique
• The shortest watchtower and related problems for polyhedral terrains
• Finding the intersection of n half-spaces in time O(n log n)
• An algorithm for generalized point location and its applications
• A linear algorithm for determining the separation of convex polyhedra
• Searching and storing similar lists
• Optimal Search in Planar Subdivisions
• Convex Analysis

This page was built for publication: Computing the shortest watchtower of a polyhedral terrain in \(O(n\log n)\) time.