Abstract
Line covering problem is a well-known topic to find the minimum number of straight lines to cover all the points to minimize the average cost in the plane. In these years, line covering has a variety of applications, in the fields such as railroad system, integer circuit (IC), sensor network and water pipes. The aim of this study is to consider the slope of line and dimensions of the input for the rectilinear line covering problems: (1) using only rectilinear line segments of the input in 2-dimensions; (2) using rectilinear directions and direction of another slope of the input in 2-dimensions; (3) using rectilinear directions in d-dimensions for d≧3. In our proofs, a main framework is obtained to prove three NP-hardness by reducing from planar 3SAT to these corresponding decision problems. In this thesis, we show that three rectilinear line covering problems are NP-complete. Apart from NP-completeness proofs, we also propose an algorithm for the general rectilinear line covering problem in 2-dimensions (GRLC-2D) and two algorithms for the rectilinear line covering problem in d-dimension (RLC-d'D) for d≧3. With a given minimum number k of lines, we know that k is size of an optimal solution. The first and second algorithm are based on fixed-parameter algorithm. We present an algorithm for GRLC-2D requiring O(2^(k+1)k!n) time and one algorithm for RLC-d'D requiring O(dk^(2k) (k+1)+dn log n) time. The third algorithm is an O(log n)-approximation algorithm in O(n log n) time.