Voronoi Diagrams Based on General Metrics in the Plane
Voronoi Diagrams Based on General Metrics in the Plane
复制标题
DOI：
10.1007/bfb0035852
复制
发表时间：
1988-02
期刊：
影响因子：
--
通讯作者：
R. Klein;D. Wood
中科院分区：
文献类型：
--
作者：
R. Klein;D. Wood
Voronoi图的基础上的度量比其他欧几里德度量或凸距离函数最近收到了相当大的兴趣，在机器人和计算几何。由于相关指标的数量很大（可能会增加，因为新的应用程序来了），一般的理论应该开发，导致的结果的结构和Voronoi图的计算，持有largeclassesof度量，而不是调查每一个案件分别在本文中，我们在这个方向上的第一步。首先给出了一种统一的定义n点Voronoi图的方法，即使两点的平分线是二维区域，其结果也总是平面在Voronoi区域中的一部分。然后，我们提出了一个简单的公理度量，保证每个可能的Voronoi区域是连接的。在这种情况下，如果平分线表现良好，则被恶意化的Voronoi图是具有n个面和O（n）个边和顶点的平面图。接下来，我们提出两个额外的公理，每个公理都确保所有的Voronoi区域是简单连通的。其中之一还意味着，由一条合适的线划分的两组点的平分线不包含回路。然后用分治算法在最优O（nlogn）步内计算出归一化Voronoi图。由此指定的度量类不仅包含所有对称凸距离函数，而且包含许多复合度量，例如，曼哈顿中城的“网格”度量L1与中央公园和哈德逊河上的欧几里得度量的组合。
Voronoi diagrams based on metrics others than the Euclidean metric or convex distance functions have recently received considerable interest in robotics and in computational geometry. Since the number of relevant metrics is large (and likely to increase, as new applications come up) a general theory should be developed, leading to results on the structure and on the computation of Voronoi diagrams that hold for largeclassesof metrics, rather than investigating each case separately.In this paper we make the first steps in this direction. First we propose a uniform way ofdefiningthe Voronoi diagram ofnpoints; the result is always apartitionof the plane inton Voronoi regions, even if the bisectors of two points are two-dimensional regions. Then we present a simple axiom for metrics that guarantees that each possible Voronoi region isconnected. In this case thenormalizedVoronoi diagram is a planar graph withnfaces andO(n) edges and vertices, if the bisectors behave well. Next we pose two additional axioms each of which ensures that all Voronoi regions aresimply-connected. One of them also implies that the bisector of two sets of points divided by a suitable line, contains no loops. Then the normalized Voronoi diagram can be computed within optimalO(nlogn) steps, using thedivide-and-conqueralgorithm. The class of metrics thereby specified does not only contain all symmetric convex distance functions but also manycompositemetrics like, for example, the combination of the “grid” metricL1in midtown Manhattan and the Euclidean metric in Central Park and on the Hudson River.