Abstract Voronoi Diagrams and their Applications
Abstract Voronoi Diagrams and their Applications
复制标题
抽象 Voronoi 图及其应用
DOI：
10.1007/3-540-50335-8_31
复制
发表时间：
1988
影响因子：
1
通讯作者：
R. Klein
中科院分区：
文献类型：
--
作者：
R. Klein
给定平面上 n 个点的集合 S，并且每两个点都有一条分离的 Jordan 曲线，可以定义抽象的 Voronoi 图 V(S)，前提是作为包含 S 的固定点的所有“半平面”的交集获得的区域是路径连接的集合，并且共同形成平面的穷举划分。这个定义不涉及任何距离的概念。底层平面图 \(\hat V\)(S) 具有 O(n) 条边和顶点。如果 S=L ∪ R 使得 \(\hat V\)(S) 中分隔 L 面和 R 面的边集不包含循环，则 \(\hat V\)(L) 和 \(\hat V\)(R) 可以在 O(n) 步骤内合并，给出 \(\hat V\)(S)。该结果意味着对于平面中的一大类度量 d，可以在最佳 O(n log n) 时间内计算 n 个点的 d-Voronoi 图。例如，这些度量包括对称凸距离函数以及由莫斯科或卡尔斯鲁厄的城市布局定义的度量。
Given a set S of n points in the plane, and for every two of them a separating Jordan curve, the abstract Voronoi diagram V(S) can be defined, provided that the regions obtained as the intersections of all the “halfplanes” containing a fixed point of S are path-connected sets and together form an exhaustive partition of the plane. This definition does not involve any notion of distance. The underlying planar graph, \(\hat V\)(S), turns out to have O(n) edges and vertices. If S=L ∪ R is such that the set of edges separating L-faces from R-faces in \(\hat V\)(S) does not contain loops then \(\hat V\)(L) and \(\hat V\)(R) can be merged within O(n) steps giving \(\hat V\)(S). This result implies that for a large class of metrics d in the plane the d-Voronoi diagram of n points can be computed within optimal O(n log n) time. Among these metrics are, for example, the symmetric convex distance functions as well as the metric defined by the city layout of Moscow or Karlsruhe.