Sign in to follow this  
sotnet

Algorithm for minimizing distance between points in two sets.

Recommended Posts

Guys, I have run into the following problem which I can't find a good algorithm for. Suppose I have a circle in 2 dimensions with a radius 1. I place points p1, p2, ..., pN in this circle at random. Each point is represented in polar coordinates as a pair (r, theta), where r can change from [0 to 1] and theta can change from [0 to 2pi). Then I take another circle and place points p`1, p`2, ..., p`N in the circle at random the same way. Now I want to a find rotation angle for 2nd circle, such that the distance between points in both circles was minimal. I can only think of a brute force algorithm. With a small step (something like 2*pi/1000), rotate all points p`i, and find the minimal distance between each pi and p`i. Any other ideas? Sincerely, Stan

Share this post


Link to post
Share on other sites
Let me give an example, so it was clear what I am trying to do.

Suppose the first circle contains just one point p1 = (1, pi), and the second circle contains a point p`1 = (1, pi/2). Then if I rotated the second circle for pi/2 degrees, points p1 and p`1 would align and distance between them would be 0.

Also, the number of points in both circles is the same.

Share this post


Link to post
Share on other sites
I'm not quite sure what you're trying to achieve here. If the points are randomly distributed, unless I'm mistaken the average distance between pi and p'i tends towards the distance between the center points of the circles as N increases. In other words, for randomly distributed points any orientation is likely as good as any other - what you're doing will only produce meaningful results I think if the points have some pattern to their distribution rather than purely random.

Share this post


Link to post
Share on other sites
Quote:
Original post by samoth
Sounds like http://en.wikipedia.org/wiki/Marriage_problem
The taxi example reads almost exactly like what I understood from your problem (taxis = circle 1, passengers = circle 2, time = polar distance). So one of the solution algorithms there should help you.


I'm not sure that this is the same problem. My understanding of the problem was that the total distance sum(pi - p'i, 0, N) should be minimized by rotating the points p' by a fixed angle. The assignment problem would find the pairs (pi, p'j) [note the different indices] such that the summed distance between the points in each pair is minimized. My assumption about the original problem may be incorrect however! :)

Share this post


Link to post
Share on other sites
So are the circles both always located at the origin? If that is the case, then you could take all of the radii, keeping track which corresponds to which point, and sort them. Then find the minimum difference between two radii of the two different circles by simply traversing through the sorted list. Now this minimum radii will also be the minimum distance and you'll just need to figure out the rotation angle, which will be easy knowing the points corresponding to the minimum radii difference.

If the circles are not centered at the same point, I'll have some other ideas ;)

Share this post


Link to post
Share on other sites
Quote:
Original post by IsoOctane
So are the circles both always located at the origin? If that is the case, then you could take all of the radii, keeping track which corresponds to which point, and sort them. Then find the minimum difference between two radii of the two different circles by simply traversing through the sorted list. Now this minimum radii will also be the minimum distance and you'll just need to figure out the rotation angle, which will be easy knowing the points corresponding to the minimum radii difference.

If the circles are not centered at the same point, I'll have some other ideas ;)


Unfortunately I don't think this is right either. This just aligns the point from each circle with the longest radius to each other, all of the other points may lie on the opposite side of the circle and thus the total distance of all the points could be greater.

As I said earlier, you can come up with any sort of heuristic you want to rotate the points, but in reality for random point configurations no one orientation is better than any other according to the original metric (as I understand it). If the metric changes, then maybe you have options :)

Share this post


Link to post
Share on other sites
Quote:
Unfortunately I don't think this is right either. This just aligns the point from each circle with the longest radius to each other, all of the other points may lie on the opposite side of the circle and thus the total distance of all the points could be greater.

As I said earlier, you can come up with any sort of heuristic you want to rotate the points, but in reality for random point configurations no one orientation is better than any other according to the original metric (as I understand it). If the metric changes, then maybe you have options :)


But does it really matter if the points are random or not, the algorithm should work on any *given* set of points, no matter how they were generated? Surely you can't come up with an orientation which would be better for any random set of points, but for a single set of known points you can. I'm not sure my algorithm will work, but I think it certainly does something more than what you suggested ;)

Share this post


Link to post
Share on other sites
Quote:
Original post by IsoOctane
But does it really matter if the points are random or not, the algorithm should work on any *given* set of points, no matter how they were generated? Surely you can't come up with an orientation which would be better for any random set of points, but for a single set of known points you can. I'm not sure my algorithm will work, but I think it certainly does something more than what you suggested ;)


Sure your algorithm does something, but it doesn't do what the OP asked :) It aligns the point in p' with the longest radius to the point in p with the longest radius. This doesn't take any of the other points into account and therefore achieves nothing with regards to minimizing the distance between corresponding points in the 2 sets, which is what the OP asked for. It is very simple to come up with a point configuration in which your algorithm makes the total distance worse.

What I'm saying is that as N increases, the average distance between randomly distributed points will tend towards the distance between the centers of the circles regardless of orientation. The original post is trying to find the global minimum of an almost flat solution space, so any result you produce is going to be practically as good as choosing an orientation at random.

Share this post


Link to post
Share on other sites
Let me add more details.

Both circles are located at origin. Both circles have the same radius.

There will be times when points are distributed randomly in each circle, and there will also be cases (more often than randomly distributed) when they are some rotation angle away.

This rotation must be applied to all the points in the second circle (my original problem has rotation symmetry (around axis perpendicular to plane of circle, and going through its origin))


I'll add another example with more points.

Example
-------

Suppose we have N = 4 (4 points).

In the first circle they might place like this:
p1 = (0.95, 0), p2 = (0.87, pi/2), p3 = (1, pi), p4 = (0.78, 3pi/2).
(Notice that they are close to r = 1, and separated by angle pi/2)

And points in the second circle might place like this:
p`1 = (1, pi/2 + alpha), p`2 = (0.92, pi + alpha), p`3 = (0.84, alpha), p`4 = (0.99, 3pi/2 + alpha), where alpha is some arbitrary angle.

Now, if I rotated all the points in the second circle by an angle -alpha (minus alpha), then they would be placed at
p`1 = (1, pi/2), p`2 = (0.92, pi), p`3 = (0.84, 0), p`4 = (0.99, 3pi/2)

It is easy to see that:
p1 is very close to p`3
p2 is very close to p`4
p3 is very close to p`2 and
p4 is very close to p`1


My goal is to find this angle 'alpha'.


Thanks!

Share this post


Link to post
Share on other sites
There isn't going to be an equation that solves this. You would need to rotate the 2nd circle in small steps for a complete revolution and keep track of the best result. The accuracy would be limited by the step size you choose, as would the speed.

Share this post


Link to post
Share on other sites
Quote:
Original post by DrEvil
There isn't going to be an equation that solves this. You would need to rotate the 2nd circle in small steps for a complete revolution and keep track of the best result. The accuracy would be limited by the step size you choose, as would the speed.


Are you sure? That's a brute force of O(step_size * n^2) algorithm.
I already have it, but it's already slow.

Here is something I found and seems promising -
"A Fast Expected Time Algorithm for the 2D Point Pattern Matching Problem":
http://www.cs.mcgill.ca/~cs644/Godfried/2005/Fall/mbouch/rubrique1.html

I am now looking into this one.

Share this post


Link to post
Share on other sites
I'm still not quite sure what the final goal is, do you wan't to find an orientation such that no other orientation will make any set of two points from different circles closer than what is the minimum of all pair distances with the goal orientation? Or do you want to minimize the sum of the distances or some such? Kind of hard to explain. If it's the former, I still think my algorithm works, I can provide some justification for that if the goal is indeed what I assumed. At least my algorithm should solve the latest example the OP gave.

Edit. Well I guess it probably wouldn't make that much sense if the goal wasn't to actually minimize the sum of the distances so I guess my assumption was wrong. Oh well...

Edit2. Forget this, the algorithm wouldn't solve the latest exmple of course, it would just align p3 to p'1 cause they have the same radius... Was assuming waaay too much and didn't even read it carefully. I'll get me coat.

[Edited by - IsoOctane on April 23, 2008 1:38:07 PM]

Share this post


Link to post
Share on other sites
You wish to minimize a target function d(σ,α), where α is the angle of rotation and σ is the permutation which binds the points of the first circle to the points of the second circle.

For any given α, there is a single σ which achieves the minimal value at that rotation angle. We'll denote this as σ*(α), which represents a function that you should know how to compute.

Since for any σ the function d(σ,x) is continuous, then the interval [0,2π) can be partitioned in a finite number of intervals where σ* is constant. Due to the nature of your problem, no two intervals have the same value of σ* (except the first and last ones, because of periodicity).

The target minimum value is reached either inside one such interval, or at the edge of such an interval. Due to obvious convexity reasons, the edges do not actually satisfy the minimum requirements, and as such your minima will occur only within intervals. Therefore, your objective is to first identify all the intervals, and then to minimize the simplified function on each interval.

Finding interval edges is simple: quasirandomly search for an interval where σ*(x) != σ*(0), which should occur fairly fast. Once you have two intervals, look for their frontier: this frontier is either a single point or an interval. Apply this frontier research recursively until all you have is individual edges (within an epsilon).

Once you have the intervals, use any technique of your choice (such as gradient descent) to find a minimum on each interval for the chosen σ*, then select the smallest of these minima.

Share this post


Link to post
Share on other sites
Quote:
Original post by ToohrVyk
snip


I'm not sure this algorithm provides any further performance guarantees over the brute force approach. You've not indicated that it did, however for the OP's benefit I thought it beneficial to clarify this. I've indicated my concerns below, it's entirely possible I've misinterpreted however.

Quote:
Original post by ToohrVyk
For any given α, there is a single σ which achieves the minimal value at that rotation angle. We'll denote this as σ*(α), which represents a function that you should know how to compute.


Unless I'm mistaken this involves solving the linear assignment problem. I've seen algorithms for this that purport to run in expected O(n) time in the number of points but I've not seen a better upper bound than O(n^3).

Quote:
Original post by ToohrVyk
Finding interval edges is simple: quasirandomly search for an interval where σ*(x) != σ*(0), which should occur fairly fast. Once you have two intervals, look for their frontier: this frontier is either a single point or an interval. Apply this frontier research recursively until all you have is individual edges (within an epsilon).


The determination of the intervals is unbounded in terms of complexity as far as I can tell. In certain point configurations it would not complete unless significant care was taken in the implementation.

Quote:
Original post by ToohrVyk
Once you have the intervals, use any technique of your choice (such as gradient descent) to find a minimum on each interval for the chosen σ*, then select the smallest of these minima.


This seems O(m*n) with m the number of intervals and n the number of points per interval, and would also depend on the number of iterations required to find each minimum.

Overall I'm not sure if this would provide better performance than the brute force approach in many cases, with the brute force approach having the advantage of an upper bound on the runtime for a given step size. Have I missed something?

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