Abstract
階層式資料結構在電腦視學、電腦圖學及影像處理領域是非常重要的資料表示技巧。為了節省記憶空間，最近有一些線性階層式結構被提出。因為線性樹狀結構缺乏指標，一些基本的運算，例如樹的建構、顯像及幾何轉換變的沒有效率。在這篇論文裹，我們是以線性樹為資料結構來設計有效率的計算方法，我們將限制在二個圖學的運算，它們是建構及顯像。首先，一個新的線性四元樹建構法將被提出，此方法將素點影像轉換至以磁碟為主的線性四元樹。此建構四元樹的時間複雜度與所有黑色節點成比例。然後依據空間相依性，我們設計一個雜序函數，此函數能夠有效地將線性四元樹轉換至它所對應的素點影像。對八元樹的建構，我們介紹一個新的建構方法，此方法利用位移掃描產生一個線性八元樹來代表物體。我們將證明建構時間與所有黑色節點成比例。由位移掃描所發展出的旋轉掃描亦被研究。最後，我們探討八元樹節點阻擋關係，發展出套節點間部份次序模組。依據這些次序，我們提出一個新的顯像方法，此方法亦可用雜序函數實現。對於一個以磁碟為主的線性樹，最主要的瓶頸是輸入╱輸出時間，因此時間複雜度是以節點被造訪次數來當作評量標準。所有我們提出的計算方法的執行時間均為Ｏ（Ｂ），它們比現有的計算方法的時間複雜度Ｏ（ｎＢ）或Ｏ（ＢｌｏｇＢ）要來的好，其中Ｂ為黑色節點個數，ｎ是解析度參數。經驗上測試結果顯示我們的計算方法在理論上及實際上對記憶體的節省及計算時間均有最佳的效率。