Algorithm for minimizing distance between points in two sets.
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.
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.
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]
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]
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.
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.
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?
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement