摘要
本文叙述作者新近发现的平面点集二阶Voronoi图的一些性质 ,并依据这些性质设计了构造二阶Voronoi图的一种算法 ,算法的时间复杂性为O(nlogn) ,优于J DBoissonnat和MYvinec所著AlgorithmicGeometry一书中提出的算法。
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.
出处
《计算机工程与科学》
CSCD
2002年第5期1-3,共3页
Computer Engineering & Science
