計算幾何學中最短和最長對角線問題之研究

Abstract

1978年,科學家Shamos提出了一個新的研究領域 :計算幾何學.這是一個結合計算機科學與幾何 學的新領域,它的目的在探討如何用計算機來 迅速地求得幾何學問題的解,例如:找包含n個給 定的點的Convex hull,找兩個多邊形的交集,以及 求兩個給定的點間的最短路徑...等問題.在這 個計畫中,我們將研究計算幾何學中的"最短對 角線"和"最長對角線"問題.我們的目的是希望 能設計出很快速的"演算法",來求出一個給定的 多邊形的最短對角線和最長對角線.