The within-strip discrete unit disk cover problem
From MaRDI portal
Publication:528480
DOI10.1016/j.tcs.2017.01.030zbMath1370.68297OpenAlexW2592261725MaRDI QIDQ528480
Alejandro López-Ortiz, Robert Fraser
Publication date: 12 May 2017
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2017.01.030
Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)
Related Items (9)
\(\mathsf{NP}\)-hardness of geometric set cover and hitting set with rectangles containing a common point ⋮ Approximability and hardness of geometric hitting set with axis-parallel rectangles ⋮ Weighted geometric set cover with rectangles of bounded integer side lengths ⋮ Discrete unit square cover problem ⋮ A constant-factor approximation algorithm for red-blue set cover with unit disks ⋮ Covering and packing of triangles intersecting a straight line ⋮ Capacitated discrete unit disk cover ⋮ Line segment disk cover ⋮ A constant-factor approximation algorithm for red-blue set cover with unit disks
Cites Work
- Unnamed Item
- Unnamed Item
- Improved results on geometric hitting set problems
- How to draw a planar graph on a grid
- Improved approximation algorithms for geometric set cover
- Homogeneous 2-hop broadcast in 2D
- Optimal packing and covering in the plane are NP-complete
- Covering a set of points in multidimensional space
- Some APX-completeness results for cubic graphs
- 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
- Linear Time Approximation for Dominating Sets and Independent Dominating Sets in Unit Disk Graphs
- A threshold of ln n for approximating set cover
- A PTAS for the Weighted Unit Disk Cover Problem
- AN IMPROVED LINE-SEPARABLE ALGORITHM FOR DISCRETE UNIT DISK COVER
- PTAS for Weighted Set Cover on Unit Squares
- Constant-Factor Approximation for Minimum-Weight (Connected) Dominating Sets in Unit Disk Graphs
- New existence proofs ε-nets
- Practical Discrete Unit Disk Cover Using an Exact Line-Separable Algorithm
- 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
- Planar Formulae and Their Uses
- The Rectilinear Steiner Tree Problem is $NP$-Complete
- NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
- A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks
- Simple heuristics for unit disk graphs
- ON THE DISCRETE UNIT DISK COVER PROBLEM
- Covering Points by Unit Disks of Fixed Location
- The Location of Emergency Service Facilities
- Approximation and Online Algorithms
- The NP-completeness column: An ongoing guide
This page was built for publication: The within-strip discrete unit disk cover problem
