A polynomial-time approximation scheme for the geometric unique coverage problem on unit squares

DOI10.1016/j.comgeo.2015.10.004zbMath1333.65021OpenAlexW2199339740MaRDI QIDQ902421

Yushi Uno, Yota Otachi, Yoshio Okamoto, Ryuhei Uehara, Takehiro Ito, Takeaki Uno, Shin-ichi Nakano

Publication date: 18 January 2016

Published in: Computational Geometry (Search for Journal in Brave)

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

zbMATH Keywords

dynamic programmingpolynomial-time approximation schemeshifting strategyunique coverage problem

Mathematics Subject Classification ID

Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Related Items

Minimum ply covering of points with disks and squares, Unique Coverage with Rectangular Regions, Minimum membership covering and hitting, Maximum independent and disjoint coverage, Exact multi-covering problems with geometric sets

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the efficiency of polynomial time approximation schemes
• Dispersion in disks
• Unit disk graphs
• Approximate algorithms for some generalized knapsack problems
• Systems of distant representatives
• A 4.31-approximation for the geometric unique coverage problem on unit disks
• Geometric red-blue set cover for unit squares and related problems
• The parameterized complexity of unique coverage and its variants
• A Polynomial-Time Approximation Scheme for the Geometric Unique Coverage Problem on Unit Squares
• Combination Can Be Hard: Approximability of the Unique Coverage Problem
• PTAS for Weighted Set Cover on Unit Squares
• Approximation schemes for covering and packing problems in image processing and VLSI
• Approximation algorithms for NP-complete problems on planar graphs
• NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques