最快的方式找到点之间最小距离 [英] Fastest way to find minimum distance between points

问题描述

我有一组二维点，并需要找到最快的方式找出哪些点对具有集合的最短距离。

I have a set of 2D points and need to find the fastest way to figure out which pair of points has the shortest distance in the set.

什么是做到这一点的最佳方法是什么？我的做法是对它们进行排序与​​快速排序，然后计算出距离。这将是O（nlogn + N）= O（nlogn）。

What is the optimal way to do this? My approach is to sort them with quicksort and then calculate the distances. This would be O(nlogn + n) = O(nlogn).

是否有可能做到这一点的线性时间？

Is it possible to do it in linear time?

感谢。

推荐答案

它实际上是的http：// EN .wikipedia.org /维基/ Closest_pair_problem

这篇关于最快的方式找到点之间最小距离的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！