Improved PTASs for convex barrier coverage

DOI10.1016/J.COMGEO.2020.101684MaRDI QIDQ5896869zbMATH OpenOpenAlexFDO

Authors Paz Carmi, Rachel Saban, Yael Stein, 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

zbMATH Keywords

barrier coveragePTASWeber problem

Mathematics Subject Classification ID

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

Recommendations

• Improved PTASs for convex barrier coverage
• Barrier Coverage with Uniform Radii in 2D
• Barrier coverage problem in 2D
• Minimizing the total cost of barrier coverage in a linear domain
• Approximation Algorithms for Barrier Sweep Coverage
• New Algorithms for Barrier Coverage with Mobile Sensors

Cites work

• A near-linear time ε-approximation algorithm for geometric bipartite matching
• Complexity of barrier coverage with relocatable sensors in the plane
• Fast approximations for sums of distances, clustering and the Fermat-Weber problem
• Improved PTASs for convex barrier coverage
• Optimal movement of mobile sensors for barrier coverage of a planar region
• The algebraic degree of geometric optimization problems
• Vertical Decomposition of Shallow Levels in 3-Dimensional Arrangements and Its Applications

Cited in

(1)

• Improved PTASs for convex barrier coverage

This page was built for publication: Improved PTASs for convex barrier coverage

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