幾何鄰近圖之研究

Abstract

在計算幾何學中，帝氏三角網圖（Delaunay triangulations）、亞畢圖（Gabriel graphs）、相互鄰近圖（relative neighborgood graphs）及歐氏最小展開樹（Eucl idean minimum spanning tree ），這四種圖形有著密切的關係。它們的關係為：帝 氏三角網圖 亞畢圖 相互鄰近圖 歐氏最小展開樹。在本篇論文裡，我們將討論相 互鄰近圖與亞畢圖及其相關的問題。 首先，我們將這兩個圖的定義域由點集合擴展的一個平面直線圖（planar straight line graph）。同時分別提出兩個需要θ（nlogn ）時間的演算法去建造他們。 接著我們放寬他們在定義中的限制條件，由此衍生出兩個新的鄰近圖（proximity graphs），分別稱為K-相互鄰近圖與K-工畢圖，K 為一個固定的正整數。同時我們也 利用2-亞畢圖與17- 亞畢圖分別去改進下列兩個歐式瓶頸問題（Euclidean bottle- neck problems ）所需的計算時間。一為建造歐氏瓶頸雙連圖（Euclidean bottlene ck biconnected edge subgraph），由原來需要O(n2) 的時間，改進到θ（nlogn ） ；另一為歐氏瓶頸配對問題（Euclidean bottlenedk matching problems），由原來 的O(n2)，改進到O（n1.5log0.5n） 。對於K-相互鄰近圖與K-亞畢圖，我們也分別提 出O（kn(nlogn)2/3 ）與O （k2nlogn ）兩個演算法，去建造它們。 最後，我們討論相互鄰近圖與亞畢圖在高維空間的幾何特性，同時也提出更有效率的 演算法去建造它們，所需的時間分別由O(n2) 與O(n3) 被改進到o(n2)與o(n3)。