VORONOI DIAGRAMS FROM CONVEX HULLS
VORONOI DIAGRAMS FROM CONVEX HULLS
复制标题
DOI：
10.1016/0020-0190(79)90074-7
复制
发表时间：
1979-01-01
影响因子：
0.5
通讯作者：
BROWN, KQ
中科院分区：
文献类型：
--
作者：
BROWN, KQ
平面Voronoi图的构造问题在许多领域都有出现，其中最近邻问题是最重要的问题之一。这包括聚类[141]，等高线图[6]和（欧几里得）最小生成树[23]。Shamos[22]提供了更多的应用程序。一个JZ （N log N）时间的最坏情况下界可以通过将其简化为排序[2 11]来表示。挑战在于构造一个O （N log N）时间的算法。Shamos[213]和Shamos anti Hoey[23]描述了一种O （N log N）时间分治算法，用于构造平面欧几里得Voronoi图。Lee和Wong[161]描述了平面中度量L1和L的O （N log N）时间算法，Drysdale和Lee[161]提出了N个线段的Voronoi图的O (N@ g N) L /*) t ' me算法（他们后来将其改进为O （N (log N)*）时间）。Shamos [2 11]， Lee和Preparata [151]， Lipton和Tarjan[171]已经产生了搜索Voronoi图（或任何其他直线平面图）的快速算法。本文描述了一种O （N log N）时间的构造平面欧几里得Voronoi图的算法，该算法可直接扩展到高维。基本的结果是，N个点的K维欧几里得Voronoi图可以通过将这些点转换到K+ i空间来构造，
The problem of construction of planar Voronoi diagrams arises in many areas, one of the most important of which is in nearest neighbor problems. This includes clustering [141, contour maps [6] and (Euclidean) minimum spanning trees [23]. Shamos [22] gives several more applications. An JZ (N log N) time worst case lower bound can be shown for this problem by reducing it to sorting [2 11. The challenge is to construct an O (N log N) time algorithm. Shamos [213 and Shamos anti Hoey [23] describe an O (N log N) time divide-and-conquer algorithm for construction of the planar Euclidean Voronoi diagram. Lee and Wong [161 describe an O (N log N) time algorithm for the L1 and L, metrics in the plane, and Drysdale pnd Lee [8] present an O (N@ g N) l/*) t’rme algorithm for the Voronoi diagram of N line segments (which they have since improved to O (N (log N)*) time). Shamos [2 11, Lee and Preparata [151, and Lipton and Tarjan [171 have produced fast algorithms for searching a Voronoi diagram (or any other straight-line planar graph). In this paper we describe an O (N log N) time algorithm for constructing a planar Euclidean Voronoi diagram which extends straightforwardly to higher dimensions. The fundamental result is that a K-dimensional Euclidean Voronoi diagram of N points can be constructed by transforming the points to K+ I-space,