Closest-point problems
Closest-point problems
复制标题
DOI：
10.1109/sfcs.1975.8
复制
发表时间：
1975-10
期刊：
影响因子：
--
通讯作者：
M. Shamos;Dan Hoey
中科院分区：
文献类型：
--
作者：
M. Shamos;Dan Hoey
研究了许多涉及平面上 N 个点的邻近性的看似无关的问题，例如寻找欧几里得最小生成树、包围集合的最小圆、k 个最近和最远邻居、两个最近点以及适当的直线三角剖分。对于大多数考虑的问题，显示了 O(N log N) 的下界。对于所有这些，当前已知的最佳上限是 O(N2) 或更糟。本文的目的是介绍一种称为 Voronoi 图的单一几何结构，它可以快速构建并仅在线性空间中包含所有相关的邻近信息。 Voronoi 图用于获得所有问题的 O(N log N) 算法。
A number of seemingly unrelated problems involving the proximity of N points in the plane are studied, such as finding a Euclidean minimum spanning tree, the smallest circle enclosing the set, k nearest and farthest neighbors, the two closest points, and a proper straight-line triangulation. For most of the problems considered a lower bound of O(N log N) is shown. For all of them the best currently-known upper bound is O(N2) or worse. The purpose of this paper is to introduce a single geometric structure, called the Voronoi diagram, which can be constructed rapidly and contains all of the relevant proximity information in only linear space. The Voronoi diagram is used to obtain O(N log N) algorithms for all of the problems.