Improved PTASs for convex barrier coverage
From MaRDI portal
Publication:5896869
DOI10.1016/j.comgeo.2020.101684zbMath1477.68464OpenAlexW3040895870MaRDI QIDQ5896869
Paz Carmi, Yael Stein, Rachel Saban, Matthew J. Katz
Publication date: 7 January 2021
Published in: Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.comgeo.2020.101684
Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)
Cites Work
- Algorithms on minimizing the maximum sensor movement for barrier coverage of a linear domain
- Minimizing the aggregate movements for interval coverage
- Optimal movement of mobile sensors for barrier coverage of a planar region
- The algebraic degree of geometric optimization problems
- Fast approximations for sums of distances, clustering and the Fermat-Weber problem
- Complexity of barrier coverage with relocatable sensors in the plane
- Optimal point movement for covering circular regions
- Vertical Decomposition of Shallow Levels in 3-Dimensional Arrangements and Its Applications
- A near-linear time ε-approximation algorithm for geometric bipartite matching
- Improved PTASs for convex barrier coverage