平面点集二阶Voronoi图的性质及算法

本文叙述作者新近发现的平面点集二阶Voronoi图的一些性质，并依据这些性质设计了构造二阶Voronoi图的一种算法，算法的时间复杂性为O（nlogn)，优于J－D Boissonna t和M Yvinec所著Algorithmic Geometry一书中提出的算法。

Property and Algorithm of the Two-Order Voronoi Diagram of a Planar Point Set

This paper describes some properties of the two order Voronoi diagram of a planar point set recently discovered by the authors, and designs an algorithm for constructing two order Voronoi diagrams according to these properties. The time complexity of this algorithm is O( n log n ). It is better than the algorithm presented in Algorithmic Geometry by J D Boissonnat and M Yvinec.