Coordinate Points. Determining the closest coordinates....

Hi, I want to find the closest set of coordinates in a plane.  I'm reading 10 million different coordinates from a file.  I need to determine which two are the closest ones.  I have solved it using brute force by storing them into an array and simply comparing each coordinate to the rest.  However since my input size is extremely big, this takes a while.  I was looking at improving the run time.  I wanted to ask you guys what would be the best way to do it...

Thanks.
LVL 1
ubuntuguyAsked:
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
ubuntuguyAuthor Commented:
Hi, I don't understand the process completely.  Can you please clarify my doubts?

ClosestPair of a set of points: Note that we     pre-sort the points according to their x coordinates
1. Divide the set into two equal sized parts by the line l, and recursively compute the minimal distance in each part.2. Let d be the minimal of the two minimal distances.   3. Eliminate points that lie farther than d apart from l   4. Sort the remaining points according to their y-coordinates   5. Scan the remaining points in the y order and compute the distances of each point to its five neighbors.   6. If any of these distances is less than d then update d.


**Part 1.  So let's say I have an array of 10,000.  I compute the median, array.length/2;  this is my l. Q: do I create an array to put the elements to the left of l in it, and then another array to put the elements to the right of l.  and to instantiate these array I would say arrayLeft[l-1] and arrayRight[array.length-l].  And my base case would be array.length ==2 that way i just compute the X distance from coordinate 1 and coordinate 2?

I don't really understand the instructions above.  Can someone please explain it Barney Style?  Thank you.
0
ozoCommented:
> I compute the median, array.length/2;  this is my l
array[array.length/2] would be the median if array was sorted left to right.
l would then be the coordinate of array[array.length/2]  that was sorted on


> And my base case would be array.length ==2 that way i just compute the  from coordinate 1 and coordinate 2?
sqrt( (X distance)^2 + (Y distance)^2 )
0
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
Java

From novice to tech pro — start learning today.

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.