The shortest watchtower and related problems for polyhedral terrains

DOI10.1016/0020-0190(88)90120-2zbMath0662.68042OpenAlexW2077906782MaRDI QIDQ1114400

Micha Sharir

Publication date: 1988

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

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

zbMATH Keywords

polyhedracomputational geometrycombinatorial complexity

Mathematics Subject Classification ID

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

Related Items

Ray shooting on triangles in 3-space, Computing the shortest watchtower of a polyhedral terrain in \(O(n\log n)\) time., Geographical information systems and location science, Guarding a terrain by two watchtowers, Computing shortest transversals, Three-dimensional weak visibility: Complexity and applications, Acrophobic guard watchtower problem, Algorithms for bichromatic line-segment problems and polyhedral terrains

Cites Work

• Unnamed Item
• Fast detection of polyhedral intersection
• Fractional cascading. I: A data structuring technique
• Counting and cutting cycles of lines and rods in space
• Finding the intersection of n half-spaces in time O(n log n)
• Optimal Point Location in a Monotone Subdivision
• Optimal Search in Planar Subdivisions