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

DOI10.1016/j.comgeo.2016.04.002zbMath1385.65022OpenAlexW2341114440MaRDI QIDQ680146

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

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

Related Items (7)

Minimum ply covering of points with disks and squares ⋮ Online unit clustering and unit covering in higher dimensions ⋮ Covering a set of points with a minimum number of equal disks via simulated annealing ⋮ Covering segments with unit squares ⋮ An exact algorithm for a class of geometric set-cover problems ⋮ Online unit covering in Euclidean space ⋮ Experiments with unit disk cover algorithms for covering massive pointsets

Cites Work

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

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