A Sweepcircle Algorithm for Voronoi Diagrams

A Sweepcircle Algorithm for Voronoi Diagrams
复制标题

DOI：
10.1007/3-540-19422-3_5
复制
发表时间：
1987-07
期刊：
--
影响因子：
--
通讯作者：
F. Dehne;R. Klein
F. Dehne;R. Klein
中科院分区：
其他
文献类型：
--
作者：
F. Dehne;R. Klein

文献摘要

被引文献

相似文献

圆锥体表面 n 个位点的 Voronoi 图具有与平面结构截然不同的组合结构。我们提出了一种扫描圆算法，可以使用线性存储在最佳时间 O(n log n) 内进行计算。
The Voronoi diagram of n sites on the surface of a cone has a combinatorial structure rather different from the planar one. We present a sweepcircle algorithm that enables its computation within optimal time O(n log n), using linear storage.