Voronoi Diagram 之新模式

A new model for the construction of Voronoi Diagram

丁秀婷(Siou-Ting Ding)

指導教授 ： 黃俊平

國立虎尾科技大學/管理學院/工業工程與管理研究所/碩士(2010年)

摘要

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 ； Bowyer-Watson Algorithm ； Divide and Conguer

並列摘要

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.

並列關鍵字

Voronoi Diagram ； Bowyer-Watson Algorithm ； Divide and Conguer

參考文獻

1.柯鈞達(2008)，基於凡諾依圖的新型無線偵測網路中繼點部署機制，國立成功大學電腦與通訊工程研究所，碩士論文。

5.Bowyer, A., (1981). “Computing Dirichlet tessellations,” The Computer Journal, Vol. 24, No. 2, pp.162–166.

7.Bentley, J. L., (1980) “Multidimensional Divide-and-Conquer,” Communications of the ACM, Vol. 23, No. 4, pp. 214-229.

8.Capart, H., Young, D.L. and Zech, Y., (2002) “ Voronoi imaging methods for the measurement of granular flows ”, Exp. Fluids, Vol. 32, pp. 121-135.

9.David, F. Watson., (1981) “Computing the n-dimensional tessellation with application to Voronoi polytopes, ” The Computer Journal, Vol. 24, No. 2, pp. 167–172.