平面上強制性相對近鄰圖問題之平行演算法

Abstract

由於硬體技術的成熟，平行處理已大幅提升了程式執行的速度，因此平行計算幾何（ Parallel Computational Geometry ）方面的研究也日形重要而迫切。本研究之目的 在探求計算幾何中相對近鄰圖問題之平行演算法。我們對原問題中輸入的點集合加以 限制，提出平面上的強制性相對近鄰圖問題，並獲得一有效之平行演算法。利用Ｏ（ N）個CREW PRAM模型上的處理器，此平行演算法可在Ｏ（log□N）時間內解出平面上 的強制性相對近鄰圖問題。