A Simple Randomized O(n log n)-Time Closest-Pair Algorithm in Doubling Metrics
A Simple Randomized O(n log n)-Time Closest-Pair Algorithm in Doubling Metrics
复制标题
倍增度量中的简单随机 O(n log n) 时间最近对算法
DOI：
10.20382/jocg.v11i1a20
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
M. Smid
中科院分区：
文献类型：
--
作者：
A. Maheshwari;Wolfgang Mulzer;M. Smid
考虑一个度量空间$（P，dist）$，其中有$N$个点，其双倍维数为常数。我们提出了一个简单的，随机的，递归的算法，计算，在$O（N \log N）$预期的时间，在$P$的最近对距离。为了生成递归调用，我们使用以前的结果Har-Peled和孟德尔，和Abam和Har-Peled计算一个稀疏的环，分开的点在一个平衡的方式。
Consider a metric space $(P,dist)$ with $N$ points whose doubling dimension is a constant. We present a simple, randomized, and recursive algorithm that computes, in $O(N \log N)$ expected time, the closest-pair distance in $P$. To generate recursive calls, we use previous results of Har-Peled and Mendel, and Abam and Har-Peled for computing a sparse annulus that separates the points in a balanced way.