Fast approximation algorithms for a nonconvex covering problem
From MaRDI portal
Publication:3776651
DOI10.1016/0196-6774(87)90012-5zbMath0636.68082MaRDI QIDQ3776651
Dorit S. Hochbaum, Wolfgang Maass
Publication date: 1987
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0196-6774(87)90012-5
approximation schemes; motion planning; robots; strongly NP-complete; minimal coverings by nonconvex objects
68Q25: Analysis of algorithms and problem complexity
68U99: Computing methodologies and applications
52C17: Packing and covering in (n) dimensions (aspects of discrete geometry)
68R99: Discrete mathematics in relation to computer science
Related Items
Unnamed Item, Unnamed Item, Algorithms for the line-constrained disk coverage and related problems, Algorithms for the line-constrained disk coverage and related problems, Approximation algorithms for maximum two-dimensional pattern matching, On point covers of \(c-\)oriented polygons, On the geometric priority set cover problem, Geometric dominating-set and set-cover via local-search, Geometric stabbing via threshold rounding and factor revealing LPs, Tighter estimates for \(\epsilon\)-nets for disks, Exact algorithms and APX-hardness results for geometric packing and covering problems, Limits of local search: quality and efficiency, Improved results on geometric hitting set problems, Fast stabbing of boxes in high dimensions, Location, pricing and the problem of Apollonius, Practical and efficient algorithms for the geometric hitting set problem, Packing and covering with non-piercing regions, Exact multi-covering problems with geometric sets, A tight analysis of geometric local search, On interval and circular-arc covering problems, Unique Covering Problems with Geometric Sets, A PTAS for the Weighted Unit Disk Cover Problem, Geometric Hitting Sets for Disks: Theory and Practice
