Covering segments with unit squares

DOI10.1016/j.comgeo.2019.01.001zbMath1468.68256arXiv1607.07256OpenAlexW2914405352MaRDI QIDQ5894547

Sasanka Roy, Ankush Acharyya, Supantha Pandit, Subhas C. Nandy

Publication date: 20 March 2019

Published in: Lecture Notes in Computer Science, Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1607.07256

zbMATH Keywords

linear programmingapproximation algorithmsNP-hardnessPTASunit squaresegment cover

Mathematics Subject Classification ID

Applications of mathematical programming (90C90) Linear programming (90C05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (7)

On dominating set of some subclasses of string graphs ⋮ Complexity and approximation for discriminating and identifying code problems in geometric setups ⋮ Covering segments with unit squares ⋮ Discriminating Codes in Geometric Setups ⋮ Line segment disk cover ⋮ Approximability of covering cells with line segments ⋮ On Covering Segments with Unit Intervals

Cites Work

• Unnamed Item
• Limits of local search: quality and efficiency
• Improved results on geometric hitting set problems
• Approximation algorithms for the unit disk cover problem in 2D and 3D
• Computational complexity of the vertex cover problem in the class of planar triangulations
• Selecting and covering colored points
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• APPROXIMATION ALGORITHMS FOR A VARIANT OF DISCRETE PIERCING SET PROBLEM FOR UNIT DISKS
• Constant Ratio Approximation Algorithms for the Rectangle Stabbing Problem and the Rectilinear Partitioning Problem
• Choice Is Hard
• AN IMPROVED LINE-SEPARABLE ALGORITHM FOR DISCRETE UNIT DISK COVER
• Approximation schemes for covering and packing problems in image processing and VLSI
• The Problem of Compatible Representatives
• Reducibility among Combinatorial Problems
• The Geometry of Scheduling
• ON THE DISCRETE UNIT DISK COVER PROBLEM
• Covering segments with unit squares

This page was built for publication: Covering segments with unit squares