Covering a set of points in multidimensional space

DOI10.1016/0020-0190(91)90075-SzbMath0748.68083MaRDI QIDQ1183467

Teofilo F. Gonzalez

Publication date: 28 June 1992

Published in: Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

polynomial-time approximation scheme\(d\)-spacehyperrectanglescovering by hypersquares

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items (24)

ON THE DISCRETE UNIT DISK COVER PROBLEM ⋮ Parallel algorithm for minimum partial dominating set in unit disk graph ⋮ AN ALGORITHMIC FRAMEWORK FOR SOLVING GEOMETRIC COVERING PROBLEMS — WITH APPLICATIONS ⋮ APPROXIMATION ALGORITHMS FOR A VARIANT OF DISCRETE PIERCING SET PROBLEM FOR UNIT DISKS ⋮ Parallel algorithms for minimum general partial dominating set and maximum budgeted dominating set in unit disk graph ⋮ Covering a set of points with a minimum number of equal disks via simulated annealing ⋮ Covering moving points with anchored disks ⋮ A PTAS for the cardinality constrained covering with unit balls ⋮ Covering Points by Unit Disks of Fixed Location ⋮ AN IMPROVED LINE-SEPARABLE ALGORITHM FOR DISCRETE UNIT DISK COVER ⋮ Approximation algorithms for the unit disk cover problem in 2D and 3D ⋮ The within-strip discrete unit disk cover problem ⋮ An improved approximation algorithm for the most points covering problem ⋮ Ectropy of diversity measures for populations in Euclidean space ⋮ A clustering-based approach to kinetic closest pair ⋮ Minimal sensor integrity: Measuring the vulnerability of sensor grids ⋮ On the Discrete Unit Disk Cover Problem ⋮ Covering uncertain points in a tree ⋮ Analysis of a first-fit algorithm for the capacitated unit covering problem ⋮ The most points connected-covering problem with two disks ⋮ An improved algorithm for online unit clustering ⋮ On interval and circular-arc covering problems ⋮ Experiments with unit disk cover algorithms for covering massive pointsets ⋮ On capacitated covering with unit balls

Cites Work

• Unnamed Item
• Optimal packing and covering in the plane are NP-complete
• Approximation schemes for covering and packing problems in image processing and VLSI
• The NP-completeness column: An ongoing guide

This page was built for publication: Covering a set of points in multidimensional space