幾何的最近點問題

Abstract

本論文主旨在於探討計算幾何學上的一些問題，所研究的問題有： （一）解析Bentley 最近點對法(closest pair algorithm)所需時間的平均表徵( average behavior)。 （二）證明基於均勻分佈的假設下Delunnay三角網(triangulation) 和最小三角網的 比是一常數。 （三）提出一求取最短跨樹(minimal spanning tree) 的並行處理方法(parallel algorithm)。 （四）探討多維排序(multidimensional sorting)的定義及相關性質。 （五）提出解決三維最近點搜尋問題(nearest neighbor searching)的新方法( algorithm)。