Fast approximation algorithms for a nonconvex covering problem

DOI10.1016/0196-6774(87)90012-5zbMath0636.68082OpenAlexW2028742519MaRDI 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

zbMATH Keywords

approximation schemesmotion planningrobotsstrongly NP-completeminimal coverings by nonconvex objects

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computing methodologies and applications (68U99) Packing and covering in (n) dimensions (aspects of discrete geometry) (52C17) Discrete mathematics in relation to computer science (68R99)

Related Items (23)

Tighter estimates for \(\epsilon\)-nets for disks ⋮ A PTAS for the Weighted Unit Disk Cover Problem ⋮ Geometric Hitting Sets for Disks: Theory and Practice ⋮ Unique Covering Problems with Geometric Sets ⋮ Improved results on geometric hitting set problems ⋮ Exact algorithms and APX-hardness results for geometric packing and covering problems ⋮ Location, pricing and the problem of Apollonius ⋮ 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 ⋮ Practical and efficient algorithms for the geometric hitting set problem ⋮ Algorithms for the line-constrained disk coverage and related problems ⋮ Packing and covering with non-piercing regions ⋮ Limits of local search: quality and efficiency ⋮ 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 ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Exact multi-covering problems with geometric sets ⋮ On interval and circular-arc covering problems ⋮ Fast stabbing of boxes in high dimensions ⋮ A tight analysis of geometric local search

This page was built for publication: Fast approximation algorithms for a nonconvex covering problem