ON THE DISCRETE UNIT DISK COVER PROBLEM
From MaRDI portal
Publication:5300002
DOI10.1142/S0218195912500094zbMath1267.68267MaRDI QIDQ5300002
Bradford G. Nickerson, Robert Fraser, Gautam K. Das, Alejandro López-Ortiz
Publication date: 24 June 2013
Published in: International Journal of Computational Geometry & Applications (Search for Journal in Brave)
Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Packing and covering in (2) dimensions (aspects of discrete geometry) (52C15) Approximation algorithms (68W25) Combinatorial complexity of geometric structures (52C45)
Related Items (14)
Tighter estimates for \(\epsilon\)-nets for disks ⋮ Minimum Dominating Set Problem for Unit Disks Revisited ⋮ Parallel algorithm for minimum partial dominating set in unit disk graph ⋮ 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 segments with unit squares ⋮ Unit disk cover problem in 2D ⋮ Discrete unit square cover problem ⋮ Limits of local search: quality and efficiency ⋮ The within-strip discrete unit disk cover problem ⋮ An exact algorithm for a class of geometric set-cover problems ⋮ Capacitated discrete unit disk cover ⋮ Line segment disk cover ⋮ Experiments with unit disk cover algorithms for covering massive pointsets
Cites Work
- Improved results on geometric hitting set problems
- Optimal packing and covering in the plane are NP-complete
- Covering a set of points in multidimensional space
- 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
- Approximation schemes for covering and packing problems in image processing and VLSI
- Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
- A Greedy Heuristic for the Set-Covering Problem
- The NP-completeness column: An ongoing guide
This page was built for publication: ON THE DISCRETE UNIT DISK COVER PROBLEM
