Solved

Coordinate Points. Determining the closest coordinates....

Posted on 2008-11-15
399 Views
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.
0
Question by:ubuntuguy

LVL 45

Accepted Solution

0

LVL 1

Author Comment

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

LVL 84

Expert Comment

> 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

Write Comment

Please enter a first name

Please enter a last name

We will never share this with anyone.

Featured Post

Suggested Solutions

For beginner Java programmers or at least those new to the Eclipse IDE, the following tutorial will show some (four) ways in which you can import your Java projects to your Eclipse workbench. Introduction While learning Java can be done with…
Okay. So what exactly is the problem here? How often have we come across situations where we need to know if two strings are 'similar' but not necessarily the same? I have, plenty of times. Until recently, I thought any functionality like that wo…
Viewers learn about how to reduce the potential repetitiveness of coding in main by developing methods to perform specific tasks for their program. Additionally, objects are introduced for the purpose of learning how to call methods in Java. Define …
This tutorial explains how to use the VisualVM tool for the Java platform application. This video goes into detail on the Threads, Sampler, and Profiler tabs.

779 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Need Help in Real-Time?

Connect with top rated Experts

11 Experts available now in Live!