Unit disk cover problem in 2D

DOI10.1016/j.jda.2015.05.002zbMath1337.68264OpenAlexW1546096012MaRDI QIDQ491638

Rashmisnata Acharyya, Gautam K. Das, Manjanna Basappa

Publication date: 18 August 2015

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2015.05.002

zbMATH Keywords

approximation algorithmcomputational geometrydiscrete unit disk cover

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Packing and covering in (2) dimensions (aspects of discrete geometry) (52C15) Approximation algorithms (68W25)

Related Items (12)

Minimum ply covering of points with disks and squares ⋮ Following a curve with the discrete Fréchet distance ⋮ Parallel algorithm for minimum partial dominating set in unit disk graph ⋮ Parallel algorithms for minimum general partial dominating set and maximum budgeted dominating set in unit disk graph ⋮ Discrete unit square cover problem ⋮ Limits of local search: quality and efficiency ⋮ An exact algorithm for a class of geometric set-cover problems ⋮ A constant-factor approximation algorithm for red-blue set cover with unit disks ⋮ Capacitated discrete unit disk cover ⋮ Line segment disk cover ⋮ A constant-factor approximation algorithm for red-blue set cover with unit disks ⋮ Discretely Following a Curve

Cites Work

• Unnamed Item
• Unnamed Item
• Improved results on geometric hitting set problems
• Homogeneous 2-hop broadcast in 2D
• Optimal packing and covering in the plane are NP-complete
• Exact and approximation algorithms for clustering
• Almost optimal set covers in finite VC-dimension
• The searching over separators strategy to solve some NP-hard problems in subexponential time
• AN IMPROVED LINE-SEPARABLE ALGORITHM FOR DISCRETE UNIT DISK COVER
• Constant-Factor Approximation for Minimum-Weight (Connected) Dominating Sets in Unit Disk Graphs
• Approximation schemes for covering and packing problems in image processing and VLSI
• ON THE DISCRETE UNIT DISK COVER PROBLEM
• Covering Points by Unit Disks of Fixed Location

This page was built for publication: Unit disk cover problem in 2D