近年來，線的覆蓋問題已經受到很多方面的應用的探討。由於線的覆蓋問題與幾何運算和圖學理論的關係越來越密切，也總是能在這些方面上提供有利的幫助。線的覆蓋問題根據目前所知，已被廣泛應用於： 鐵路系統、電路系統和感應器…等。然而，我們發現在某些的自然情況下，一般的任意線覆蓋問題會受到環境的影響。因此，在利用度上產生大大的不方便。所以在此論文中，我們採用了正交線的覆蓋取代了原本的一般任意線覆蓋問題。因此，在此篇論文中，我們延伸出了三個有關正交線的覆蓋的問題，並且也證明了這些問題都屬於NP-hard的問題。除此之外，我們對於此NP-hard問題，也提出了三個演算法作為解決，這些演算法主要的基礎來源為fixed-parameter演算法和近似演算法。在fixed-parameter演算法的運用上，我們採用了bounded search tree的方法，去除了一些不可能的情況，藉此降低計算上的時間。而在近似演算法方面，由於線性覆蓋問題可以由集合覆蓋問題的演算法，經由巧妙的修改而解決，但是由於修改的方面過於複雜，故在此論文中，我們提出了一個直接對於正交線覆蓋問題的近似演算法，藉此移除了需要由集合覆蓋問題的解決方法所需的轉化過程。

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.

Contents
1 Introduction . . . . .. . . . . .. . . . . . . . 4
1.1 Related Work . . . . .. . . . . . . . . . . . . 5
1.2 Motivations . . . . . .. . . . . . . . . . . . 8
1.3 Problem Denition . . .. . ... . . . . . . . . 8
1.4 Our Contribution . . .. . .. . . . . . . . . . 10
1.5 Outline . . . . . . . . . . . . . . .. . . . . 11
2 Preliminaries . . . . . . . . . . . . . .. . . . 12
3 NP-completeness Results . . . . .. . . . . . . . 15
3.1 Hardness of RLS . . . . ... . . . .. . . ... . 16
3.2 Hardness of RLLS . . . . . .. . . . .. . . . 20
3.3 Hardness of RLC-d'D . . . . .. . . . .. . . . 26
4 Algorithms . . . . . . . . . . . .. . . . . . . .34
4.1 Fixed-Parameter Algorithm for GRLC-2D . . .. . 35
4.2 Fixed-Parameter Algorithm for RLC-d'D . . .. . 39
4.2.1 A Deterministic Algorithm . . . . . . . 39
4.2.2 Improved Algorithm . . . . . . . . . . . 43
4.3 O(log n)-Approximation for RLC-d'D . . . . . 46
5 Concluding Remarks 49

Bibliography

[1] N. Megiddo, and A. Tamir. On the Complexity of Locating Linear Facilities in the Plane. Operation Research Letters. November 1982, Pages: 194-197.

[2] S. Langerman, and P. Morin. Covering Things with Things. Discrete and Computational Geometry. April 2005, Pages: 717-729.

[3] M. Grantson, and C. Levcopoulos. Covering a Set of Points with a Minimum Number of Lines. Algorithms and Complexity. May 2006, Pages: 6-17.

[4] W. Ke, B. Liu, and M. Tsai, Constructing a Wireless Sensor Network to Fully Cover Critical Grids by Deploying Minimum Sensors on Grid Points Is NP-Complete. IEEE Transactions on Computers. May 2007, Pages: 710-715.

[5] L. Guibas, M. Overmars, J. Robert. The Exact Fitting Problem in Higher Dimensions. Computational Geometry. July 1996, Pages: 215-230.

[6] V. Kumar, S. Arya, and H. Ramesh. Hardness of Set Cover With Intersection 1. In: Automata Languages and Programming. 1853, Pages: 624-635.

[7] R. Downey, and M. Fellows. Parameterized Complexity. Bull. Symbolic Logic. 2002, Pages: 528-529.

[8] D.S. Johnson. Approximation Algorithms for Combinatorial Problems. Journal of Computer
System Science. 1974, Pages: 256-278.

[9] N. Sarnak, and R. Tarjan. Planar Point Location Using Persistent Search Tree. Communications of the ACM. July 1986, Pages: 669-679.

[10] D. Nussbaum. Rectilinear p-piercing problems. International Conference on Symbolic and Algebraic Computation. 1997, Pages: 316-323.

[11] M. Sharir, and E. Welzl. Rectilinear and polygonal p-piercing and p-center problems. Annual Symposium On Computational Geometry. 1996, Pages: 122-132.

[12] D. Lichtenstein. Planar Formulae and Their Uses. SIAM Journal on Computing. 1982, Pages: 329-343.

[13] V. Kumar, and H. Ramesh. Covering Rectilinear Polygons with Axis-Parallel Rectangles. Annual ACM Symposium on Theory of Computing. 1999, Pages: 445-454.

[14] S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. Proof Verifcation and Intractability of Approximation Problems. IEEE Symposium on Foundations of Computer Science. 1992, Pages: 13-22.

[15] M. Bellare, S. Goldwasser, C. Lund, A. Russell. Ecient Probabilistically Checkable Proofs
and Applications to Approximation. ACM Symposium on Theory of Computing. 1993, Pages: 294-303.

[16] Y. Cheng, S. Iyengar, and R. Kashyap. A New Method for Image compression using Irreducible Covers of Maximal Rectangles. IEEE Transactions on Software Engineering. 1988, Pages: 651-658.

[17] R. Hassin, and N. Megiddo. Approximation Algorithms for Hitting Objects with Straight Lines. Discrete Applied Mathematics. 1991, Pages: 29-42.

[18] C. Levcopoulos. Improved Bounds for Covering General Polygons by Rectangles. Foundations of Software Tech. and Theoretical Comp. Sc. 1987.

[19] J. Chen, I. Kanj, and W. Jia. Vertex cover: further observations and further improvements. Journal of Algorithms. November 2001, Pages: 280-301.

[20] D. Estrin, R. Govindan, J. Heidemann, and S. Kumar. Next Century Challenges: Scalable Coordination in Sensor Networks. ACM International Conference on Mobile Computing and Networking. 1999.

[21] J. Kahn, R. Katz, and K. Pister, Nexst. Century Challenges: Mobile Networking for Smart
Dust. ACM International Conference on Mobile Computing and Networking. 1999.

[22] A. Cerpa, J. Elson, D. Estrin, L. Girod, M. Hamilton, and J. Zhao. Habitat Monitoring: Application Driver for Wireless Communications Technology. ACM SIGCOMM Workshop on
Data Communications. 2001.

[23] M. Carey, and D. Johnson. Computers and Intractability: A Guide to the Theory of NP-completeness. Freeman, San Francisco. 1979.

[24] C. Lund, and M. Yannakakis. On the Hardness of Approximating Minimization Problems. ACM Symposium on Theory of Computing. 1993, Pages: 286-293.

[25] S. Durocher, C. Gray, and J. King. Minimizing the Number of Arcs Linking a Permutation of Points in the Plane. CCCG. 2006, Pages: 181-184.
of Points in the Plane. CCCG. 2006, Pages: 181-184.