Abstract
在本文中，我們探討有關階層式空間資料結構在超立方體機器上的平行建構與處理。首先，我們研究對於空間資料在超立方體架構上的映對方法，一般而言，將空間資料映對到一個特定的平行架構包含兩個過程：一是將所給的資料做一適當的切割；其次是將切割後的資料分派給對應的處理器計算處理。對於一個ｋ維的空間分割，我們提出一個較好的計算結構，稱為binomial-n tree 。同時，將空間資料的幾何相鄰關係一併於分割過程中考慮，我們得到一個將binomial-n tree映對到超立方體上的演算法，而且利用超立方體的連接方式，保持空間資料之相鄰關係。這種映對演算法除了使分割過程更有效率外，並且能加速後序的平行演算法。 在超立方體上我們提出比濟耳曲面的產生與塗彩平行演算法，並說明保持相鄰關係的映對方式之優點。其中我們比較三種不同分派原則的映對方式（geometric adjacency mapping ，Morton scan code mapping ，binaryreflective gray code ），藉由理論及實驗證明，幾何相鄰的映對方式有較好的效益。 根據平行空間分割的觀念，我們亦在超立方體架構上提出一新的分散式四元樹結構，同時也提出一個有效率的建構演算法，藉由適當的資料分派，我們證明將這種分散式四元樹結構映對到超立方體上可以保持二維的階層相鄰關係。許多電腦繪圖及影像處理的運算可以因為這種分散式四元樹結構及保持相鄰關係的特性而加快運算速度。理論分析及實驗均證明我們所提出的方法在時間及資訊交換上均較優越。從二維四元樹推廣至三維八元樹，我們亦提出一在超立方體上的平行八元樹建構演算法，利用超立方體上的分散式八元樹結構，對一給定的實體資料，我們也提出一有效率的平行等值面產生的演算法。