Approximation algorithms for the unit disk cover problem in 2D and 3D

DOI10.1016/J.COMGEO.2016.04.002MaRDI QIDQ680146zbMATH OpenOpenAlexFDO

Authors Juan-Miguel Gracia

Publication date 22 January 2018

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.comgeo.2016.04.002

zbMATH Keywords

complexityapproximation algorithmsunit ball coverunit disk cover

Mathematics Subject Classification ID

Complexity and performance of numerical algorithms (65Y20) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Recommendations

• Unit disk cover problem in 2D
• On the discrete unit disk cover problem
• On the discrete unit disk cover problem
• An improved line-separable algorithm for discrete unit disk cover
• Practical Discrete Unit Disk Cover Using an Exact Line-Separable Algorithm

Cites work

• A dynamic fixed windowing problem
• Almost optimal set covers in finite VC-dimension
• An Almost Linear Time 2.8334-Approximation Algorithm for the Disc Covering Problem
• Approximation schemes for covering and packing problems in image processing and VLSI
• Covering a set of points in multidimensional space
• Decomposable searching problems I. Static-to-dynamic transformation
• Optimal packing and covering in the plane are NP-complete
• Optimal partition trees

Cited in

(18)

• Minimum ply covering of points with disks and squares
• Algorithms for the line-constrained disk coverage and related problems
• Algorithms for the line-constrained disk coverage and related problems
• Approximation algorithms for the class cover problem
• A 4.31-approximation for the geometric unique coverage problem on unit disks
• Online unit clustering and unit covering in higher dimensions
• An Almost Linear Time 2.8334-Approximation Algorithm for the Disc Covering Problem
• Polynomial time approximation schemes for minimum disk cover problems
• Practical Discrete Unit Disk Cover Using an Exact Line-Separable Algorithm
• Covering a set of points with a minimum number of equal disks via simulated annealing
• Approximation algorithms for minimum ply covering of points with unit squares and unit disks
• A constant-factor approximation for multi-covering with disks
• Two optimization problems for unit disks
• APPROXIMATION ALGORITHMS FOR A VARIANT OF DISCRETE PIERCING SET PROBLEM FOR UNIT DISKS
• Experiments with unit disk cover algorithms for covering massive pointsets
• An optimal algorithm for the minimum disc cover problem
• An exact algorithm for a class of geometric set-cover problems
• The within-strip discrete unit disk cover problem

This page was built for publication: Approximation algorithms for the unit disk cover problem in 2D and 3D

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