关键词: Voronoi 图, 细分算法, 增量算法, 栅格扩张法, 区间算术

Abstract: Voronoi diagram is one of the most important concepts in computational geometry,
It is applied widely in computer graphics, computational geometry, computer aided geometric
design, finite element grid partition, robot trajectory control, pattern recognition, meteorology and
geology. Based on quadtree data structure and interval arithmetic technique, a new subdivision
algorithm for Voronoi diagram of a planar point set is proposed. A comparison of this subdivision
algorithm with the well known incremental algorithm and grid expansion method is conducted.
Test results show that the subdivision algorithm is more efficient. The most important is that the
idea of subdivision algorithm is very simple and therefore it is easy to implement.

Key words: Voronoi diagram, subdivision algorithm, incremental algorithm, grid expansion
method, interval arithmetic