幾何問題中之退化現象

Abstract

解決計算幾何學上的問題所提出的演算法通常會省略對退化現象的考慮。但是當要將 這些演算法選寫成程式以解決幾何上的問題時，除了理論上的演算法所處理的一般狀 況之外，程式設計師還必須要考慮輸入資料中的退化現象以撰寫出可正確執行的程式 。在本論文中，我們將探討在計算幾何學上，一種稱之為判別型態的退化現象（bran -ch-type degeneracy） 。首先我們敘述二個處理判別型態退化現象的方法，稱之為 SoS和SpS。如果程式設計師能夠應用這些方法來撰寫程式，那他所寫的程式就像理論 上的演算法所描述般地不用考慮到各個退化現象的處理，而且所撰寫出的程式對任何 型態符合的輸入資料（包括退化現象）都能夠正確地執行。接著我們證明在某些修件 下這二個方法，SoS和SpS，是一樣的。最後我們實地應用SoS 來撰寫程式以解決三個 平面幾何的問題： （一）．線與多邊形相交（line-polygon intersections），（二）．凸面殼（conv -ex hulls） 以及（三）．Voronoi 網狀圖╱Delaunay三角化。應用SoS（或SpS）所 撰寫的程式比直接、各別處理各個判別型態退化現象所撰寫的程式要來得簡潔和周密 。對計算出凸面殼或建立Voronoi 網狀圖╱Delaunay三角化而言，如果輸入的資料是 隨機產生的，實驗的數據顯示這二種不同寫法的程式所需要的執行時間相近。