Point Line Segment Cover

Abstract

In this thesis, we consider the Point Line Segment Cover problem in a parameterized setting. In this problem, we have to decide for a given set of points in the plane, and an integer k, whether all points can be covered by at most k disjoint non-intersecting line segments. This problem is a more constrained version of the well studied Point Line Cover problem. We introduce new concepts, such as Reserved Line Segments and Hybrid Points, which are used to prove that the Point Line Segment Cover is kernelizable, with a kernel size of O(k^6). This also implies that the Point Line Segment Cover problem is Fixed Parameter Tractable. In this thesis, we also give an algorithm that solves the kernelized instance. The theory has been implemented and experimented with, and through solving various instances it is shown that the kernelization step can significantly decrease the solving time for small values of k.