The shortest watchtower and related problems for polyhedral terrains

DOI10.1016/0020-0190(88)90120-2MaRDI QIDQ1114400zbMATH OpenOpenAlexFDO

Authors Micha Sharir

Publication date 1988

Published in Information Processing Letters (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Full work available at URL https://doi.org/10.1016/0020-0190(88)90120-2

zbMATH Keywords

combinatorial complexitycomputational geometrypolyhedra

Mathematics Subject Classification ID

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

Recommendations

• Computing the shortest watchtower of a polyhedral terrain in \(O(n\log n)\) time.
• 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

• Counting and cutting cycles of lines and rods in space
• Fast detection of polyhedral intersection
• Finding the intersection of n half-spaces in time O(n log n)
• Fractional cascading. I: A data structuring technique
• scientific article; zbMATH DE number 3926242 (Why is no real title available?)
• Optimal Point Location in a Monotone Subdivision
• Optimal Search in Planar Subdivisions

Cited in

(15)

• Algorithms for bichromatic line-segment problems and polyhedral terrains
• Three-dimensional weak visibility: Complexity and applications
• Routing in a polygonal terrain with the shortest beacon watchtower
• Shortest watchman tours in simple polygons under rotated monotone visibility
• Acrophobic guard watchtower problem
• Ray shooting on triangles in 3-space
• Computing the shortest watchtower of a polyhedral terrain in \(O(n\log n)\) time.
• scientific article; zbMATH DE number 1796960 (Why is no real title available?)
• Geographical information systems and location science
• Guarding a terrain by two watchtowers
• Guarding precise and imprecise polyhedral terrains with segments
• Guarding points on a terrain by watchtowers
• On the discrete and semi-continuous versions of the two-watchtower problem in the plane
• Computing shortest transversals
• Guarding polyhedral terrain by k-watchtowers

This page was built for publication: The shortest watchtower and related problems for polyhedral terrains

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