Guarding a terrain by two watchtowers

DOI10.1007/s00453-008-9270-3zbMath1204.68239OpenAlexW1995551793MaRDI QIDQ5961974

Simeon C. Ntafos, Pankaj K. Agarwal, Sergey Bereg, Ovidiu Daescu, Micha Sharir, Haim Kaplan, Binhai Zhu

Publication date: 16 September 2010

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-008-9270-3

zbMATH Keywords

computational geometryparametric searchterrain guardingvisibility algorithms

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items

Parametric search: three new applications, Acrophobic guard watchtower problem

Cites Work

• Maintaining visibility of a polygon with a moving point of view
• Finding the upper envelope of n line segments in O(n log n) time
• Range searching with efficient hierarchical cuttings
• Improved approximation algorithms for geometric set cover
• Visibility and intersection problems in plane geometry
• Computing all large sums-of-pairs in \(\mathbb R^n\) and the discrete planar two-watchtower problem
• Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
• The shortest watchtower and related problems for polyhedral terrains
• Parallel computational geometry
• Computing the shortest watchtower of a polyhedral terrain in \(O(n\log n)\) time.
• Applying Parallel Computation Algorithms in the Design of Serial Algorithms
• Slowing down sorting networks to obtain faster sorting algorithms
• A Constant‐Factor Approximation Algorithm for Optimal 1.5D Terrain Guarding
• Inapproximability results for guarding polygons and terrains
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item