Complexity and Algorithms on Rectilinear Line Cover Problem

正交線覆蓋問題的複雜度與演算法

陳俊傑(Juin-Jae Chen)

指導教授 ： 潘雙洪

國立清華大學/電機資訊學院/資訊工程學系/碩士(2011年)

摘要

近年來，線的覆蓋問題已經受到很多方面的應用的探討。由於線的覆蓋問題與幾何運算和圖學理論的關係越來越密切，也總是能在這些方面上提供有利的幫助。線的覆蓋問題根據目前所知，已被廣泛應用於： 鐵路系統、電路系統和感應器…等。然而，我們發現在某些的自然情況下，一般的任意線覆蓋問題會受到環境的影響。因此，在利用度上產生大大的不方便。所以在此論文中，我們採用了正交線的覆蓋取代了原本的一般任意線覆蓋問題。因此，在此篇論文中，我們延伸出了三個有關正交線的覆蓋的問題，並且也證明了這些問題都屬於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.

並列關鍵字

Line covering problem ； computational geometry ； graph theory

參考文獻

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

[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.

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