phil1882 Posted May 20, 2014 Report Share Posted May 20, 2014 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? Quote Link to comment Share on other sites More sharing options...

0 bonanova Posted May 21, 2014 Report Share Posted May 21, 2014 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. 1 Quote Link to comment Share on other sites More sharing options...

0 k-man Posted May 21, 2014 Report Share Posted May 21, 2014 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_{1}). 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. Quote Link to comment Share on other sites More sharing options...

0 bonanova Posted May 21, 2014 Report Share Posted May 21, 2014 k-man, you're right. I took the problem as minimizing the number of Pythagorean steps, even if doing O(n^{2}) simpler ones. I like your approach. You do programming and algorithms better than I do. Quote Link to comment Share on other sites More sharing options...

## Question

## 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?

## Link to comment

## Share on other sites

## 3 answers to this question

## Recommended Posts

## Join the conversation

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