  We study several variations of line segment covering problem with
axis-parallel unit squares in $I\!\!R^2$. A set $S$ of $n$ line segments is
given. The objective is to find the minimum number of axis-parallel unit
squares which 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 some variations, we have polynomial time
exact algorithms. 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 factor 16 approximation result based on multilevel linear programming
relaxation technique, which may be useful for solving some other problems.
Further, we show that our problems have connections with the problems studied
by Arkin et al. 2015 on conflict-free covering problem. Our NP-completeness
results hold for more simplified types of objects than those of Arkin et al.
2015.
