Guarding a terrain by two watchtowers
From MaRDI portal
Publication:5961974
DOI10.1007/s00453-008-9270-3zbMath1204.68239MaRDI 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
68U05: Computer graphics; computational geometry (digital and algorithmic aspects)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- 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