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

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.

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.

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.

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! :)

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 ;)

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 :)

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 ;)

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.

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!