Abstract
樹狀資料結構如四元樹及八元樹已是電腦視覺、計算機圖學、影像處理、卡通圖學、及地理資訊系統常用的表示法, 近年來, 已有一些線性樹狀結構被提出, 用來節省儲存所需的記憶體空間。在線性樹狀結構中, 由於指標已被刪除, 一些涉及尋鄰的基本運算已不再便捷, 於是在線性樹狀資料結構中尋鄰問題乃成為一值得研究的課題。在本論文中, 我們將針對線性樹狀結構, 設計出有效率的尋鄰方法。首先, 我們提出一個針對線性四元樹的尋鄰方法, 在隨機影像模型下: 其平均時間複雜度會被一常數所束縛, 而該方法的主要關鍵在於選取適當的尋找區間。緊接著, 我們發展出一種轉換的方法, 該轉換使得傳統四元樹演算法可用以處理線性四元樹的影像; 我們將以連結部份標籤的問題作為一個例子, 用來展示該轉換; 已有多篇論文討論該問題在線性四元樹上的解法, 我們選擇其中一種較有效率的演算法作為比較對象: 從我們的實驗可知, 轉換過的演算法較節省時間。我們拓展線性四元樹尋鄰的觀念, 推導出線性八元樹尋鄰的方法。利用此尋鄰方法,我們發展出一個求取邊界的演算法; 該問題已存在相當有效率的解法, 但是由我們的實驗及分析, 可知其平均時間複雜度為0(B log B), 而我們的演算法只需要0(B), 其中的B 代表節點個數。最後, 我們將提出一種0(1)的尋鄰方法, 該方法使用一個特殊的資料結構。目前也存在0(1)的尋鄰方法, 但是相較之下, 它使用更多的記憶體空間, 所能解決的問題也較有限。