Covering segments with unit squares

0534822 - ÚI 2021 NL eng J - Článek v odborném periodiku
Acharyya, Ankush - Nandy, S. C. - Pandit, S. - Roy, S.
Covering segments with unit squares.
Computational Geometry-Theory and Applications. Roč. 79 (2019), s. 1-13. ISSN 0925-7721. E-ISSN 1879-081X
Klíčová slova: approximation algorithms * Segment cover * Unit square * NP-hardness * Linear programming * Approximation algorithms
Impakt faktor: 0.476, rok: 2019

We study several variations of line segment covering problem with axis-parallel unit squares in the plane. Given a set S of n line segments, the objective is to find the minimum number of axis-parallel unit squares that cover at least one end-point of each segment. The variations depend on the orientation and length of the input segments. We prove some of these problems to be NP-complete, and give constant-factor approximation algorithms for those problems. For the general version of the problem, where the segments are of arbitrary length and orientation, and the squares are given as input, we propose a 16-approximation algorithm based on multilevel linear programming relaxation technique. More precisely, we reduce this problem to the problem of covering points in the plane by a given set of unit squares using linear programming relaxation technique. A linear programming-based 8-approximation algorithm for the later problem yields a 16-approximation result for the former problem. This technique may be of independent interest in solving some other problems.
Trvalý link: http://hdl.handle.net/11104/0312984