CODEWITHSUNDEEP
mathcoordinates
Madfish
Madfish

Reputation: 85

N points are given in Euclidean plane. For each point, find the smallest distance between itself and the other points

The problem is simple: n points are given in Euclidean plane by their coordinates. For each point, you should find the smallest distance between itself and any of the other points, using Euclidean distance. This minimum distance is called the radius for that point. For each point we should return two things:

  1. The radius(r).

  2. The number of points (excluding itself) which have the Euclidean distance less that or equal to 2*r.

Restrictions on the input:

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

Well, I have done this in o(n^2). Does anyone have a better solution ??

Examples:

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)

Upvotes: 0

Views: 999

Answers (1)

John Alexiou
John Alexiou

Reputation: 29244

First, recognize that distances are symmetric. The distance of i to j is the same as the distance of j to i. In total there are n*(n-1)/2 distances to calculate.

If you pre-compute them with the following loop, then any further processing, like scanning for the closest, is going to be super fast.

// 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]);                    
    }
}

and not to get the distance between two points i and j is fast.

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];
    }
}

The calculation index = -i*(i-2*n+1)/2+(j-i)-1 is explained as follows. We are only storing the upper triangular values of the matrix with the distances. Each row i has row=n-i-1 values, and the index of the first value (closest to the diagonal) is start=sum(n-t-1,t=0,i-1) = -i*(i-2*n+1)/2. The index of the j column is index = start + j- i -1 as the difference in column position between j and the one next to the diagonal.

For example with n=4 there are only 6 values to store. The index for the distance array for each pair calculates as follows:

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

So to get the distance between i=1 and j=3, the above has index=4 and distances[index] is the needed value. Note that -i*(i-2*n+1)/2+(j-i)-1 = -1*(1-2*4+1)/2+(3-1)-1 = 4

- Reference post: https://stackoverflow.com/a/9040526/380384 for symmetric matrices in packed form, but ones that store the upper triangular values and the diagonals. So, similar but not exact.

Essentially the above cuts the processing by half compared to the naive approach of a double nested loop over all the pairs.

Upvotes: 0

Related Questions