Voronoi Diagram是幾何空間分析上非常有用的工具,常應用於空間區域問題與解決最近相鄰點的問題,其應用領域包含資訊工程、機械工程、建築、藝術、生物學、藥理學、化學、材料科學等。過去有許多學者提出建構Voronoi Diagram的演算法,也運用divide and conquer解決小區域的Voronoi Diagram之運算。但是divide and conquer只是將運算區域分割與縮小,並未對點的增減提出討論。此外,大部份學者所提出的演算法都是O(n log n)的複雜度。因此,本文提出一個新的演算法建構Voronoi Diagram,並將其複雜度從O(n log n)縮小到趨於線性的複雜度。除此之外,在已建構的二維平面Voronoi Diagram的圖形中,若增減點數至此圖形時,也能明確的找出那些點才是真正影響此點區域的關鍵點,並針對影響的點數重新建構,以減少不必要的計算及降低複雜度,使二維平面Voronoi Diagram的圖形能在最少的步驟下完成,而省略了又要重新針對全部的點做建構。由此可知,使用本研究所提出的方法建構Voronoi Diagram,不僅能降低複雜度,還能快速的重新建構。
Voronoi Diagram is an important tool for geometrical analysis, that is often applied to the metric space problems containing information engineering, mechanical engineering, architecture, art, biology, pharmacology, chemistry, materials science, etc. Many researchers proposed algorithms for the construction of Voronoi Diagram based on divide and conquer technique. But the divide and conquer technique deals only with the construction of Voronoi Diagram, that doesn’t take the modifications of Voronoi Diagram into account. In addition, the complexity of the algorithm is O(n log n). The complexity of the proposed algorithm is close to linear. The adding of new points or removing of the given points can be identified easily according to the proposed algorithm that gives an efficient solution to the modification of the Voronoi Diagram.