• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 423
  • Last Modified:

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

1 Solution
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.
> 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 )

Featured Post

Free Tool: Site Down Detector

Helpful to verify reports of your own downtime, or to double check a downed website you are trying to access.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Tackle projects and never again get stuck behind a technical roadblock.
Join Now