Sign in to follow this  
Followers 0

shortest distance

4 posts in this topic

Posted · Report post

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?

0

Share this post


Link to post
Share on other sites

Posted · Report post

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.

1

Share this post


Link to post
Share on other sites

Posted · Report post

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.

0

Share this post


Link to post
Share on other sites

Posted · Report post

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.

0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0

  • Recently Browsing   0 members

    No registered users viewing this page.