N точек даны в евклидовой плоскости.Для каждой точки найдите наименьшее расстояние между собой и другими точками

Question

Проблема проста: n точки даны в евклидовой плоскости по своим координатам.Для каждой точки вы должны найти наименьшее расстояние между собой и любой другой точкой, используя евклидово расстояние.Это минимальное расстояние называется радиусом для этой точки.Для каждой точки мы должны вернуть две вещи:

1. Радиус (r).

2. Количество точек (исключая себя), которыеЕвклидово расстояние должно быть меньше или равно 2*r.

Ограничения на входе:

1 <= number of coordinates <= 30000
0 <= x,y <= 10000

Что ж, я сделал это в o(n^2).У кого-нибудь есть лучшее решение ??

Примеры:

1. n=3
(0,0)
(0,0)
(3,4)

output-
(0.00 1)
(0.00 1)
(5.00 2)

2. n=5
(5,3)
(7,8)
(0,9)
(3,1)
(4,4)

output-
(1.41 2)
(5.00 4)
(6.40 4)
(2.83 2)
(1.41 1)

Answer 1

Во-первых, признайте, что расстояния симметричны.Расстояние от i до j равно расстоянию от j до i.Всего нужно вычислить n*(n-1)/2 расстояний.

Если вы предварительно вычислите их с помощью следующего цикла, то любая дальнейшая обработка, например, поиск ближайшего, будет очень быстрой.

// n = number of points
distances=new float[n*(n-1)/2];
int index = 0;
for (int i = 0; i<n-1; i++)
{
    for (int j = i+1; j<n; j++)
    {
        // This is by far the most expensive operation to make:
        distances[index++]=Vector2.Distance(Points[i], Points[j]);                    
    }
}

и не получить расстояние между двумя точками i и j быстро.

class PointCloud
{

    int n;
    float[] distances;

    float GetDistance(int i, int j)
    {
        if(i==j) return 0;
        if(i>j) return GetDistance(j ,i);
        int index = -i*(i-2*n+1)/2+(j-i)-1;
        return distances[index];
    }
}

Расчет index = -i*(i-2*n+1)/2+(j-i)-1 объясняется следующим образом.Мы храним только верхние треугольные значения матрицы с расстояниями.Каждая строка i имеет значения row=n-i-1, а индекс первого значения (ближайший к диагонали) равен start=sum(n-t-1,t=0,i-1) = -i*(i-2*n+1)/2.Индекс столбца j равен index = start + j- i -1 как разница в положении столбца между j и рядом с диагональю.

Например, для n=4 сохраняются только 6 значений.Индекс для массива расстояний для каждой пары рассчитывается следующим образом:

  j=0      j=3
| *  0  1  2 | i=0
| 0  *  3  4 |
| 1  3  *  5 |
| 2  4  5  * | i=3

Таким образом, чтобы получить расстояние между i=1 и j=3, приведенное выше имеет index=4 и distances[index] - необходимое значение,Обратите внимание, что -i*(i-2*n+1)/2+(j-i)-1 = -1*(1-2*4+1)/2+(3-1)-1 = 4

_{- Ссылка: https://stackoverflow.com/a/9040526/380384 для симметричных матриц в упакованном виде, но те, которые хранят верхние треугольные значения и диагоналей.Таким образом, аналогично, но не точно.}

По существу вышесказанное сокращает обработку вдвое по сравнению с наивным подходом двойного вложенного цикла по всем парам.