# Algorithm for minimizing distance between points in two sets.

## Recommended Posts

sotnet    122
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 p1, p2, ..., pN 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 pi, and find the minimal distance between each pi and pi. Any other ideas? Sincerely, Stan

##### Share on other sites
sotnet    122
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 p1 = (1, pi/2). Then if I rotated the second circle for pi/2 degrees, points p1 and p1 would align and distance between them would be 0.

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

##### Share on other sites
d00fus    328
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 on other sites
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.

##### Share on other sites
d00fus    328
Quote:
 Original post by samothSounds like http://en.wikipedia.org/wiki/Marriage_problemThe 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 on other sites
IsoOctane    122
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 on other sites
d00fus    328
Quote:
 Original post by IsoOctaneSo 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 on other sites
IsoOctane    122
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 on other sites
d00fus    328
Quote:
 Original post by IsoOctaneBut 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 on other sites
sotnet    122

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:
p1 = (1, pi/2 + alpha), p2 = (0.92, pi + alpha), p3 = (0.84, alpha), p4 = (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
p1 = (1, pi/2), p2 = (0.92, pi), p3 = (0.84, 0), p4 = (0.99, 3pi/2)

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

My goal is to find this angle 'alpha'.

Thanks!

##### Share on other sites
DrEvil    1148
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 on other sites
sotnet    122
Quote:
 Original post by DrEvilThere 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.

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 on other sites
IsoOctane    122
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 on other sites
ToohrVyk    1596
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 on other sites
d00fus    328
Quote:
 Original post by ToohrVyksnip

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 ToohrVykFor 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 ToohrVykFinding 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 ToohrVykOnce 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?