Abstract
四元樹（quadtrees ）不管是在影像處理（image processing）、電腦圖學（compu-ter graphics）、或圖形辨識（pattern recognition ）等方面，都是一種極為重要的表示法。它是一種階層式的資料結構，具有以一節點來代表一群聚在一起之同色圖元的特性。這與二元陣列（binary array）比較，不僅具有節省空間的好處，更可加速處理的速度。目前己有許多有關四元樹的演算法被提出，但在此眾多己發表的演算法中，相鄰節點的找尋（neighbor finding）一直扮演著如基石般的角色。就指標四元樹（pointer-based quadtrees ）。SAMET 已在１９８２年提出一影響深遠的相鄰節點找尋技巧演算法，同時也建構了非常漂亮的機率模型（probability model ）來加以分析。但對於益形重要的線性四元樹（linear quadtrees），至今除極少數文獻偶而在文章中穿插幾句話，評其需log （N ）的搜尋時間外，尚無人做過這方面的研究。本篇論文即針對此問題做詳盡的探討與分析。首先，對任一給定的節點（a given n-ode ），將欲找尋的相鄰節點（neighbor node ）分成大於等於或小於給定節點；再依相鄰節點位於給定節點的垂直、水平、角落（corner）、或對角（diagonal）等方向分別討論。相鄰節點的四元碼（quadcode）、最近的共同祖先（the nearest com-mon ancestor）、和給定節點中與相鄰節點相接的圖元座標等，都將被算出。利用此結果，對任意大小或方向的相鄰節點我們均可界定出一必包含相鄰節點的搜尋範圍，只要在此範圍內尋找，便可找到相鄰節點，否則便是不存在此相鄰節點。最後，假定以二元搜尋（binary search ）法在此範圍中搜尋此相鄰節點，則借用SAMET 所建構的機率模型，我們能精確地分析出，其在平均的情況下，所需的節點比較次數之上限（upper bound ），皆被一很小的數值所限制住。實驗測試的結果更遠小於我們所求得的上限。