BrainDen.com - Brain Teasers
• 0

# shortest distance

## Question

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?

## Recommended Posts

• 0

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 Dmin.

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

Disregard all point pairs for which D > 1.414 Dmin.

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

##### Share on other sites

• 0

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 Dmin.

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

Disregard all point pairs for which D > 1.414 Dmin.

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(xk - x1,, yk - y1).

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.

##### Share on other sites

• 0

k-man, you're right.

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

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

## Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

×   Pasted as rich text.   Paste as plain text instead

Only 75 emoji are allowed.

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.