A SWEEPLINE ALGORITHM FOR VORONOI DIAGRAMS
A SWEEPLINE ALGORITHM FOR VORONOI DIAGRAMS
复制标题
DOI：
10.1007/bf01840357
复制
发表时间：
1987-01-01
期刊：
影响因子：
1.1
通讯作者：
FORTUNE, S
中科院分区：
文献类型：
--
作者：
FORTUNE, S
我们提出了一个变换，可用于计算Voronoi图的Sweepline技术。变换是用来获得简单的算法计算Voronoi图的点的网站，线段的网站，和加权点的网站。所有算法都有O（nlogn）最坏情况运行时间和O（n）空间。
We present a transformation that can be used to compute Voronoi diagrams with a sweepline technique. The transformation is used to obtain simple algorithms for computing the Voronoi diagram of point sites, of line segment sites, and of weighted point sites. All algorithms haveΟ(nlogn) worst case running time and useΟ(n) space.