完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.author | 蘇東興 | en_US |
dc.contributor.author | SU, DONG-XING | en_US |
dc.contributor.author | 張瑞川 | en_US |
dc.contributor.author | ZHANG, RUI-CHUAN | en_US |
dc.date.accessioned | 2014-12-12T02:06:51Z | - |
dc.date.available | 2014-12-12T02:06:51Z | - |
dc.date.issued | 1989 | en_US |
dc.identifier.uri | http://140.113.39.130/cdrfb3/record/nctu/#NT782394042 | en_US |
dc.identifier.uri | http://hdl.handle.net/11536/54574 | - |
dc.description.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)。 | zh_TW |
dc.language.iso | zh_TW | en_US |
dc.subject | 幾何學 | zh_TW |
dc.subject | 帝氏三角網圖 | zh_TW |
dc.subject | 亞畢圖 | zh_TW |
dc.subject | 相互鄰近圖 | zh_TW |
dc.subject | 歐氏最小展開樹 | zh_TW |
dc.subject | 平面直線圖 | zh_TW |
dc.subject | 歐氏瓶頸問題 | zh_TW |
dc.subject | DELAUNAY-TRANGULATIONS | en_US |
dc.subject | GABRIEL-GRAPHS | en_US |
dc.subject | RELATIVE-NEIGHBORHOOD-GRAPHS | en_US |
dc.subject | EMST | en_US |
dc.subject | PLANAR-STRAIGHTLINE-GRAPH | en_US |
dc.subject | EUCLIDEAN-BOTTLENECK-PROBLEMS | en_US |
dc.title | 幾何鄰近圖之研究 | zh_TW |
dc.type | Thesis | en_US |
dc.contributor.department | 資訊科學與工程研究所 | zh_TW |
顯示於類別: | 畢業論文 |