shortest distance

[phil1882]

you are given a list of 100 coordinates, and asked to use the pathageoran theorm he fewest number of times to determine the shortest distance between any two. is it an n^2 problem, or can you do better? how much better?

[bonanova]

I'm assuming that by "shortest distance between any two points"

is meant "distance between the two closest points."

Create a half-matrix of n(n-1)/2 values of D = max (dx, dy) for each pair of points.

Find the pair for which D is minimal and equal to D_min.

An upper bound of the distance for that pair is D_min Sqrt(2) = 1.414 D_min.

Disregard all point pairs for which D > 1.414 D_min.

Now calculate using Pythagoras the actual distance d only for the remaining pairs.

[k-man]

I'm assuming that by "shortest distance between any two points"

is meant "distance between the two closest points."

Create a half-matrix of n(n-1)/2 values of D = max (dx, dy) for each pair of points.

Find the pair for which D is minimal and equal to D_min.

An upper bound of the distance for that pair is D_min Sqrt(2) = 1.414 D_min.

Disregard all point pairs for which D > 1.414 D_min.

Now calculate using Pythagoras the actual distance d only for the remaining pairs.

this is still an O(n^2) solution that requires n^2 computations of max(dx,dy).

1. Sort all points in order of their x coordinate. Sort the points that have the same x by y. This can be done in n*log(n) steps

2. Iterate through the sorted array of points and calculate the distance from the first point to all other points up to point k, keeping track of the lowest distance found so far. Point k is determined when the known shortest distance is less than max(x_k - x_1,, y_k - y₁).

3. Repeat step 2 for the second point and so on for all other points.

I didn't try to figure out the order of complexity of this algorithm, but it should be less than n^2 since we're stopping each iteration before reaching the end of the array. We need to figure out the expected value of k to get the idea of how efficient this algorithm is.

[bonanova]

k-man, you're right.

I took the problem as minimizing the number of Pythagorean steps, even if doing O(n²) simpler ones.

I like your approach. You do programming and algorithms better than I do.