平面點上的支配關係（domination relation ）是一種部分順序關係（partiall
ordered relation），有許多的問題可以靠著解決某些支配問題而得到答案，如：矩
形視域問題（rectangular visibility problem），最長相同子句問題（the longe-
st common subsequence problem ），線段包含問題（interval closure problem）
，矩形相容問題（rectangle containment problem ）。在本篇論文中我們解決三個
支配問題並且描述他們的應用，首先我們去找平面點集合中最長的一條鏈（the lon-
gest chain in planar points set ），藉此解決最長相同子句問題，接下來考慮直
接支配問題（the direct domination problem ），我們提出一種優雅的方法並且有
些結果比前人還要好，更者，用這結果可以解決矩形視域問題，最後，我們發現一種
個個擊破（divide and conquer）的演算法則解決了所有直接支配配對的問題（all
direct domination prais problem ）。令X 是平面點集合，關係＞是支配關係。事
實上，我們考慮的這些支配問題可以視作波集合〔X ，＞〕（partilly orderde set
），而所有波集合可以利用Hasse diagram 來表示。我們所解決的三個問題，其實是
找Hasse diagram 上的最長路徑（longest path），祖先（prdedcessor ），和所有
的邊（edges ）。
|