Fast approximation algorithms for a nonconvex covering problem

DOI10.1016/0196-6774(87)90012-5MaRDI QIDQ3776651zbMATH OpenOpenAlexFDO

Authors 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 schemesminimal coverings by nonconvex objectsmotion planningrobotsstrongly NP-complete

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 4215407
• scientific article; zbMATH DE number 3888915
• On the Complexity of Nonconvex Covering
• Approximation schemes for covering and packing problems in image processing and VLSI
• Close approximations of minimum rectangular coverings

Cited in

(28)

• 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
• Tighter estimates for -nets for disks
• Unique covering problems with geometric sets
• scientific article; zbMATH DE number 3888915 (Why is no real title available?)
• scientific article; zbMATH DE number 4215407 (Why is no real title available?)
• A PTAS for the Weighted Unit Disk Cover Problem
• Geometric hitting sets for disks: theory and practice
• On the Complexity of Nonconvex Covering
• Approximation schemes for covering and packing problems in image processing and VLSI
• Exact algorithms and APX-hardness results for geometric packing and covering problems
• Covering clients with types and budgets
• Optimality of geometric local search
• Limits of local search: quality and efficiency
• 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
• Improved results on geometric hitting set problems
• 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
• Approximation and parameterized algorithms for covering with disks of two types of radii

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

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