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

DOI10.1016/S0925-7721(96)00009-0MaRDI QIDQ2482906zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• The shortest watchtower and related problems for polyhedral terrains
• Guarding a terrain by two watchtowers
• Guarding a terrain by two watchtowers
• scientific article; zbMATH DE number 1796960
• Guarding polyhedral terrain by k-watchtowers

Cites work

• scientific article; zbMATH DE number 4211552 (Why is no real title available?)
• scientific article; zbMATH DE number 4151829 (Why is no real title available?)
• scientific article; zbMATH DE number 177829 (Why is no real title available?)
• A linear algorithm for determining the separation of convex polyhedra
• An algorithm for generalized point location and its applications
• Convex Analysis
• Finding the intersection of n half-spaces in time O(n log n)
• Fractional cascading. I: A data structuring technique
• Optimal Search in Planar Subdivisions
• Searching and storing similar lists
• The shortest watchtower and related problems for polyhedral terrains

Cited in

(11)

• Parametric search: three new applications
• Inapproximability of finding maximum hidden sets on polygons and terrains
• Approximation algorithms for terrain guarding.
• scientific article; zbMATH DE number 1796960 (Why is no real title available?)
• Guarding precise and imprecise polyhedral terrains with segments
• Routing in a polygonal terrain with the shortest beacon watchtower
• Guarding a terrain by two watchtowers
• The shortest watchtower and related problems for polyhedral terrains
• Guarding polyhedral terrain by k-watchtowers
• Three-dimensional weak visibility: Complexity and applications
• Acrophobic guard watchtower problem

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2482906)