摘要
線段簡化的在多數領域都有廣泛的應用，例如地理資訊系統、圖形處理、大型積體電路設計以及資料壓縮。在此議題中，計算出一線段數最少且符合所指定的距離誤差值是相當著名的問題。此類問題我們稱其為最少線段數簡化問題(min-# problem)。在本篇論文中，我們針對現段簡化的問題分別套用三種不統的選點標準，其分別為：(1) 只使用輸入的點, (2) 可使用現段上任意點, (3) 可使用平面上的任意點。此三種標準我們分別套用在矩狀線和一般多邊形線段。首先，我們證明了簡化多條矩狀線的問題是一個NPC的問題。在此系列證明中，我們只使用常數長度的單調(monotone)線段來達成證明。另外我們也進一步的提出了另外三種一般線段的NPC證明。在以上的證明中，其中有兩個我們大幅簡化了前人的證明方式。所有的證明中，我們有系統且一致性的利用Planar monotone 3SAT來完成所有的證明。除了NPC的證明外，我們另外提出了多個線段最佳簡化的演算法。對於多邊形線段或矩形線段只有一常數k的量，若我們使用選點標準(1)，則我們可以得到一O(kn^(4k+1))時間複雜度的演算法。而若輸入是k條矩狀線，且選點標準為(2)或(3)，則我們提出一時間複雜度為O(kn^(6k+1))的演算法。
並列摘要
The problem of simplifying a planar subdivision has a broad range of applications, in areas such as geographic information systems (GIS), image processing, VLSI design and data compression. A well-known problem is to compute a simplification using the minimum number of segments, while ensuring that every point of the simplification is within some specified error distance to the original subdivision. This problem is usually called the min-# problem. In this thesis, we consider three separate vertex-selection criteria (models) for the simplification: (1) using only the vertices of the input subdivision, (2) using any point on the edges of the input, (3) using any points in the plane. We consider two categories of problems by applying these criteria to rectilinear and general subdivisions, respectively. First we show that the three variants for simplifying rectilinear subdivisions are all NP-complete. In the proofs, only monotone polylines with a constant number of segments are used in the construction. We further show that the three variants for simplifying general subdivisions are also all NP-complete. In the proofs, only monotone polylines with at most four segments are used. Two of these three proofs largely simplify the previously known NP-complete proofs for the corresponding problems. We obtain a unified proof framework to prove the above six NP-hardness by reducing from planar monotone 3SAT to the corresponding problems. Apart from these NP-completeness proofs, we propose several optimal algorithms for simplifying rectilinear planar subdivisions. For a constant number k of rectilinear or general x- monotone polylines, we present an O(kn^(4k+1))-time algorithm to solve the simplification problems for criterion (1), and an O(kn^(6k+1))-time algorithm for criteria (2) and (3).
參考文獻
[1] Pankaj K. Agarwal, Sariel Har-peled, Nabil H. Mustafa, and Yusu Wang. Near-linear time
approximation algorithms for curve simplification. 2002.
[2] Pankaj K. Agarwal and Kasturi R. Varadarajan. Efficient algorithms for approximating polygonal
chains. Discrete & Computational Geometry, 23(2):273–291, 2000.
and Bettina Speckmann. Area-preserving approximations of polygonal paths. Journal of