Optimal point movement for covering circular regions

DOI10.1007/s00453-013-9857-1zbMath1325.68248arXiv1107.1012OpenAlexW1673927286MaRDI QIDQ2354019

Xue-Hou Tan, Haitao Wang, Danny Z. Chen, Gangshan Wu

Publication date: 10 July 2015

Published in: Algorithmica, Algorithms and Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1107.1012

zbMATH Keywords

algorithmsdata structurescomputational geometrycircular convex bipartite graphmobile sensorsbarrier coveragecircular region coveragedynamic maximum matching

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items

A fast FPTAS for two dimensional barrier coverage using sink-based mobile sensors with MinSum movement, Algorithms on minimizing the maximum sensor movement for barrier coverage of a linear domain, Approximation algorithm for MinSum linear barrier coverage with sink-based mobile sensors on the plane, Improved PTASs for convex barrier coverage, Minimizing the aggregate movements for interval coverage, Minimizing the total cost of barrier coverage in a linear domain, Algorithms for covering multiple barriers

Cites Work

• Representing a functional curve by curves with fewer peaks
• Optimal slope selection via expanders
• Optimal movement of mobile sensors for barrier coverage of a planar region
• A linear-time algorithm for a special case of disjoint set union
• Efficient algorithms for finding maximum matchings in convex bipartite graphs and related problems
• Randomized optimal algorithm for slope selection
• Solving the Euclidean bottleneck matching problem by \(k\)-relative neighborhood graphs
• Circular convex bipartite graphs: Maximum matching and Hamiltonian circuits
• Computing Euclidean bottleneck matchings in higher dimensions
• A linear time algorithm for maximum matchings in convex, bipartite graphs
• Dynamic Matchings in Convex Bipartite Graphs
• New Algorithms for Barrier Coverage with Mobile Sensors
• Applying Parallel Computation Algorithms in the Design of Serial Algorithms
• An Optimal-Time Algorithm for Slope Selection
• Linear and Time Minimum-Cost Matching Algorithms for Quasi-Convex Tours
• Slowing down sorting networks to obtain faster sorting algorithms
• Necklaces, Convolutions, and X + Y
• Geometry helps in bottleneck matching and related problems
• A RANDOMIZED ALGORITHM FOR SLOPE SELECTION