Abstract
本論文探討單調多邊形包容判定問題（Monotone Polygon Containment Decision P-roblem），即決定一個多邊形能否經由平移放入另一個單調多邊形，而不需求出整個可行區域（Feasible Region ）。我們部份解決了Baker 等人所提出的Open problem，即多邊形包容問題，如只判定可行性是否有比求出整個可行區域更迅速的方法。我們證實至少在直交雙凹多邊形的包容問題上的確如此。我們提出一個０（nm log m）的演算法來解決直交凸多邊形（Rectilinearly Convex）的包容決定問題，其中n 是外包多邊形的邊數，m 是內含多邊形的邊數。這個演算法能在移動中法定第一個可行落點（Feasible Placement），然後停止，因此比較迅速。同時，經修改後可用來解決直交雙凹多邊形（Rectilinearly ２－concave ）的包容問題。求出整個可行區域的演算法其複雜度（Time Complexity ）為０（nm lognm +k），其中 是整個可行區域的邊數。在最差情形下（Worst-case），k 高達。如僅決定可行與否，則演算法的複雜度為０(ｎｍｌｏｇ2ｎｍ)。 從這個例子，可以看出如只判斷可行性，解法確較迅速。另外，我們也提出一個解決單調多邊形包容問題的演算法，複雜度為０(ｎｍlogｍ)。由於可行區域的邊數有nm，這一演算法接近optimal 。