Need help with a maths problem!
Moderators: NeilBlanchard, Ralf Hutter, sthayashi, Lawrence Lee
Need help with a maths problem!
hi all
i realise this is a bit of a long shot, but for the math/geometry geniuses out there i need help with a seemingly simple problem
imagine a path made up of circles of varying diameter. some circles are close together, others further apart. the problem involves finding the shortest path from the first circle to the last circle, touching (or going through) each of the inbetween circles in order, a bit like this:
i know the position and radius of each circle, so i know it's solvable  my brain just can't seem to figure out a working algorithm!
any ideas anyone??
i realise this is a bit of a long shot, but for the math/geometry geniuses out there i need help with a seemingly simple problem
imagine a path made up of circles of varying diameter. some circles are close together, others further apart. the problem involves finding the shortest path from the first circle to the last circle, touching (or going through) each of the inbetween circles in order, a bit like this:
i know the position and radius of each circle, so i know it's solvable  my brain just can't seem to figure out a working algorithm!
any ideas anyone??
Can't help you out with a full algorithm... but maybe this will help. This is the simplest part of the algorithm (eliminating colinear circles like #2 from the list) but the rest of it is actually really difficult... the intersection point of the line with a particular circle is not just dependent on the circles either side but on every single circle, right to either end of the list. e.g. considering #4, moving circle #6 would change the optimal intersection point on circle #5, which would mean that #4's optimal intersection point changes too. (I typed out the steps below before realising this.... so point #1 wouldn't be true unless you were looking at either end of the list (circle #1 or #6 in the example))
What's this for? It sounds too difficult to be a uni assignment (I'm studying engineering and I'm not sure how I'd go about implementing an algorithm for this).
Anyway, here's a way you could eliminate redundant, colinear circles like #2
1. The line (if extended) would necessarily pass through the first circle's centre. I can't prove it... but consider any placement of the other circles and you'd see this were true too. If an extension of the line didn't pass through the centre of the 1st circle, it would be longer than necessary.
2. Thence you would want to consider the next circle, and find the range of ray angles from the first circle that would also pass through the next circle. You could do this by comparing the centre of the next circle to the centre of the first circle to get the middle of the angle range, and then using inverse tan to find the magnitude of the range either side of the middle of the range. However, you wouldn't draw the line connecting the circles yet.
3. Repeat step 2  first you would've compared the angle range of #2 from #1, next compare the angle range of #3 from number #1. Basically what you're trying to do is finding where the 'colinearity' of the circles stops. In this example, #1#3 are colinear but not #4. Comparing #2 with #1 would give you a pretty wide range of angles, comparing #3 with #1 then narrows it down. Step 2 is repeated until you find a circle whose angle range from #1 no longer intersects with the narroweddown angle range (that you've found by examining #2 and #3).
What's this for? It sounds too difficult to be a uni assignment (I'm studying engineering and I'm not sure how I'd go about implementing an algorithm for this).
Anyway, here's a way you could eliminate redundant, colinear circles like #2
1. The line (if extended) would necessarily pass through the first circle's centre. I can't prove it... but consider any placement of the other circles and you'd see this were true too. If an extension of the line didn't pass through the centre of the 1st circle, it would be longer than necessary.
2. Thence you would want to consider the next circle, and find the range of ray angles from the first circle that would also pass through the next circle. You could do this by comparing the centre of the next circle to the centre of the first circle to get the middle of the angle range, and then using inverse tan to find the magnitude of the range either side of the middle of the range. However, you wouldn't draw the line connecting the circles yet.
3. Repeat step 2  first you would've compared the angle range of #2 from #1, next compare the angle range of #3 from number #1. Basically what you're trying to do is finding where the 'colinearity' of the circles stops. In this example, #1#3 are colinear but not #4. Comparing #2 with #1 would give you a pretty wide range of angles, comparing #3 with #1 then narrows it down. Step 2 is repeated until you find a circle whose angle range from #1 no longer intersects with the narroweddown angle range (that you've found by examining #2 and #3).
[size=92][b]Laptop:[/b] Macbook Pro  Core Duo @ 1.83ghz  2gb DDR  100gb @ 7200rpm  [b]MacOS/WinXP dualboot[/b]
[b]Desktop:[/b] Northwood C @ 3.0ghz [i]Passive[/i] w/ Scythe Ninja  Abit IC7G  2gb DDR  X800Pro  Samsung 160gb (suspended)  2x Nexus 12cm
[b]Server:[/b] A64 Venice 3000+ @2.16ghz/1.25V  DFI RS482  512mb  Samsung 200gb  Maxtor 250gb  WD 300gb[/size]
[b]Desktop:[/b] Northwood C @ 3.0ghz [i]Passive[/i] w/ Scythe Ninja  Abit IC7G  2gb DDR  X800Pro  Samsung 160gb (suspended)  2x Nexus 12cm
[b]Server:[/b] A64 Venice 3000+ @2.16ghz/1.25V  DFI RS482  512mb  Samsung 200gb  Maxtor 250gb  WD 300gb[/size]
thanks for the response jb_ interesting to hear from another aussie (let alone sydneysider) first!
i appreciate your thoughts on eliminating/ignoring colinear circles  that was actually the first step i took as well essentially drawing rays of possible directions and then narrowing it down by "looking through" the nearest circle to the next, and so on.
using this approach, it appeared that when the angle of rays is as small as it can go, something needs to happen at the first 'narrowing' of the longest current ray (at some circle C) to allow the rays to 'turn' and thus open up more angles to make a turn of some sort. unfortunately the arrival and departure points that lie on this circle C seem to be almost always different, and the fact that all regions are circles certainly doesn't help.
a simplification i'm using at the moment involves replacing each circle of diameter d with a square of side length d; this eases the load on the brain quite a lot.
this isn't for a uni assignment, more a project i'm undertaking on my own. i finished uni (software engineering) 2 years ago, and apart from some math courses i did i'd have to agree that this would seem hard for a uni assignment. unfortunately, this is still only a simple step, as the final algorithm will also have to consider the weight of each line (which changes between points)  but we'll ignore that for now.
i appreciate your thoughts on eliminating/ignoring colinear circles  that was actually the first step i took as well essentially drawing rays of possible directions and then narrowing it down by "looking through" the nearest circle to the next, and so on.
using this approach, it appeared that when the angle of rays is as small as it can go, something needs to happen at the first 'narrowing' of the longest current ray (at some circle C) to allow the rays to 'turn' and thus open up more angles to make a turn of some sort. unfortunately the arrival and departure points that lie on this circle C seem to be almost always different, and the fact that all regions are circles certainly doesn't help.
a simplification i'm using at the moment involves replacing each circle of diameter d with a square of side length d; this eases the load on the brain quite a lot.
this isn't for a uni assignment, more a project i'm undertaking on my own. i finished uni (software engineering) 2 years ago, and apart from some math courses i did i'd have to agree that this would seem hard for a uni assignment. unfortunately, this is still only a simple step, as the final algorithm will also have to consider the weight of each line (which changes between points)  but we'll ignore that for now.
No problems, sorry if it sounded a little basic.
Because of the nature of this problem (I think it would be called a multivariate optimisation?) I don't think there's a cutanddried algorithm that would produce the correct answer with one iteration.
You know you've got the shortest path when the angles made by the line with the tangent to the circle where it intersects, are equal as the line approaces the circle and as it leaves the circle. Maybe this could be the basis for an iterative process where you just plonk the line anywhere on the circle, and then repeatedly going through the list of circles, moving the intersection point to where the angles with the tangent on either side are equal. 1000 iterations and you'd get pretty close to the optimal solution. Or, since with each iteration the reduction in total line length approaches zero, you could just keep iterating until the delta goes under a certain threshold.
(Funny that, I'm studying SE too [though combined with commerce, majoring in finance]!)
Because of the nature of this problem (I think it would be called a multivariate optimisation?) I don't think there's a cutanddried algorithm that would produce the correct answer with one iteration.
You know you've got the shortest path when the angles made by the line with the tangent to the circle where it intersects, are equal as the line approaces the circle and as it leaves the circle. Maybe this could be the basis for an iterative process where you just plonk the line anywhere on the circle, and then repeatedly going through the list of circles, moving the intersection point to where the angles with the tangent on either side are equal. 1000 iterations and you'd get pretty close to the optimal solution. Or, since with each iteration the reduction in total line length approaches zero, you could just keep iterating until the delta goes under a certain threshold.
(Funny that, I'm studying SE too [though combined with commerce, majoring in finance]!)
[size=92][b]Laptop:[/b] Macbook Pro  Core Duo @ 1.83ghz  2gb DDR  100gb @ 7200rpm  [b]MacOS/WinXP dualboot[/b]
[b]Desktop:[/b] Northwood C @ 3.0ghz [i]Passive[/i] w/ Scythe Ninja  Abit IC7G  2gb DDR  X800Pro  Samsung 160gb (suspended)  2x Nexus 12cm
[b]Server:[/b] A64 Venice 3000+ @2.16ghz/1.25V  DFI RS482  512mb  Samsung 200gb  Maxtor 250gb  WD 300gb[/size]
[b]Desktop:[/b] Northwood C @ 3.0ghz [i]Passive[/i] w/ Scythe Ninja  Abit IC7G  2gb DDR  X800Pro  Samsung 160gb (suspended)  2x Nexus 12cm
[b]Server:[/b] A64 Venice 3000+ @2.16ghz/1.25V  DFI RS482  512mb  Samsung 200gb  Maxtor 250gb  WD 300gb[/size]
As a starting point for the above process, you could use the point on a particular circle (e.g. #4) that lies on the line connecting the centre of that circle (#4) with the midpoint of the line connecting the centres two adjacent circles (#3 and #5). That'd give a rough approximation from which you could iteratively optimise.
[size=92][b]Laptop:[/b] Macbook Pro  Core Duo @ 1.83ghz  2gb DDR  100gb @ 7200rpm  [b]MacOS/WinXP dualboot[/b]
[b]Desktop:[/b] Northwood C @ 3.0ghz [i]Passive[/i] w/ Scythe Ninja  Abit IC7G  2gb DDR  X800Pro  Samsung 160gb (suspended)  2x Nexus 12cm
[b]Server:[/b] A64 Venice 3000+ @2.16ghz/1.25V  DFI RS482  512mb  Samsung 200gb  Maxtor 250gb  WD 300gb[/size]
[b]Desktop:[/b] Northwood C @ 3.0ghz [i]Passive[/i] w/ Scythe Ninja  Abit IC7G  2gb DDR  X800Pro  Samsung 160gb (suspended)  2x Nexus 12cm
[b]Server:[/b] A64 Venice 3000+ @2.16ghz/1.25V  DFI RS482  512mb  Samsung 200gb  Maxtor 250gb  WD 300gb[/size]
*sigh* ... an iterative approach is looking more and more appealing the more i think about the problem...
do you think an iterative approach would adapt well if each section of line coming off a circle was weighted differently? i admit i'm having a bit of difficulty visualising an iterative approach (though not by fault of your explanation)  and as such would rather avoid spending time on it if it ultimately can't be used.
i imagine that the iterative approach would be O(n) or O(n^2), which is reasonable enough given that i don't expect there to be more than 200300 circles in any single calculation (typically around 50100). i was also thinking of a brute force solution where you split each circle up into a circular arrangement of p points, and test each possible path... however this is obviously inefficient (O(p^n) without optimisation)
do you think an iterative approach would adapt well if each section of line coming off a circle was weighted differently? i admit i'm having a bit of difficulty visualising an iterative approach (though not by fault of your explanation)  and as such would rather avoid spending time on it if it ultimately can't be used.
i imagine that the iterative approach would be O(n) or O(n^2), which is reasonable enough given that i don't expect there to be more than 200300 circles in any single calculation (typically around 50100). i was also thinking of a brute force solution where you split each circle up into a circular arrangement of p points, and test each possible path... however this is obviously inefficient (O(p^n) without optimisation)
i understand and agree with this point now. the way i'm visualising it in my head is to draw a line through all of the midpoints, and 'tighten' it by pulling it through the start midpoint and end midpoint. what you would end up with is a series of connected, straight lines which would be the answer.jb_ wrote:1. The line (if extended) would necessarily pass through the first circle's centre. I can't prove it... but consider any placement of the other circles and you'd see this were true too. If an extension of the line didn't pass through the centre of the 1st circle, it would be longer than necessary.
so easy to say and to visualise... hard to algorithmify

 Posts: 2049
 Joined: Thu Dec 15, 2005 11:06 am
 Location: Klamath Falls, OR
IMHO this is not a traveling salesman problem  because order of circles is know beforehand (or did I misunderstand?). This is just nasty problem to formalize in easily computable way.

edit: some kind of possible solution or at least little idea:
Sorry, but I don't know math terms in english  if something is wrong or not understandable, please correct and ask.
Assume:
1. N+1 circles have center coordinates X0(n),Y0(n) and radiuses R(n), n in [0,N]
2. every circle crosses line at one point, creating angle A(n), A(n) in [0,2*pi)
3. intersection point has coordinates X(n),Y(n), which can be calculated from:
X(n)=X0(n)+R(n)*sin(A(n))
Y(n)=Y0(n)+R(n)*cos(A(n))
NB! We can safely assume that every circle intersects line in one point  we can just skip other point, if it exists
4. line length L(n)=sqrt((X(n)X(n1))^2+(Y(n)Y(n1))^2), n in [1,N]
5. we need minimize sum(L(n)) by changing A(n)
Iterative solution, let S(s) mean sum(L(n)) at step s, s in [0,...] (look at edit2):
0. set inital values A(n)=0, s=0, calculate S(0)
1. for each n in [1,N] find min(L(n)) by changing A(n1) (ideally by differentiating, but can be iteratively too)
2. for n=N find min(L(N)) by changing A(N)
3. set s=s+1, calculate S(s)
4. if abs(S(s)S(s1))>precision goto step 1
Problems:
1. there's no proof that such iteration will converge  result sum can be oscillating
2. there's no proof that even iteration converges, then it converges enough fast to find actual minimum value (before iteration will be cancelled by reaching given precision)

edit2: somewhat better iteration:
0. set inital values A(n)=0, s=0, calculate S(0)
1. for n=0 find min(L(1)) by changing A(0)
2. for each n in [1,N1] find min(L(n)+L(n+1)) by changing A(n) (ideally by differentiating, but can be iteratively too)
3. for n=N find min(L(N)) by changing A(N)
4. set s=s+1, calculate S(s)
5. if abs(S(s)S(s1))>precision goto step 1
This should converge faster

edit: some kind of possible solution or at least little idea:
Sorry, but I don't know math terms in english  if something is wrong or not understandable, please correct and ask.
Assume:
1. N+1 circles have center coordinates X0(n),Y0(n) and radiuses R(n), n in [0,N]
2. every circle crosses line at one point, creating angle A(n), A(n) in [0,2*pi)
3. intersection point has coordinates X(n),Y(n), which can be calculated from:
X(n)=X0(n)+R(n)*sin(A(n))
Y(n)=Y0(n)+R(n)*cos(A(n))
NB! We can safely assume that every circle intersects line in one point  we can just skip other point, if it exists
4. line length L(n)=sqrt((X(n)X(n1))^2+(Y(n)Y(n1))^2), n in [1,N]
5. we need minimize sum(L(n)) by changing A(n)
Iterative solution, let S(s) mean sum(L(n)) at step s, s in [0,...] (look at edit2):
0. set inital values A(n)=0, s=0, calculate S(0)
1. for each n in [1,N] find min(L(n)) by changing A(n1) (ideally by differentiating, but can be iteratively too)
2. for n=N find min(L(N)) by changing A(N)
3. set s=s+1, calculate S(s)
4. if abs(S(s)S(s1))>precision goto step 1
Problems:
1. there's no proof that such iteration will converge  result sum can be oscillating
2. there's no proof that even iteration converges, then it converges enough fast to find actual minimum value (before iteration will be cancelled by reaching given precision)

edit2: somewhat better iteration:
0. set inital values A(n)=0, s=0, calculate S(0)
1. for n=0 find min(L(1)) by changing A(0)
2. for each n in [1,N1] find min(L(n)+L(n+1)) by changing A(n) (ideally by differentiating, but can be iteratively too)
3. for n=N find min(L(N)) by changing A(N)
4. set s=s+1, calculate S(s)
5. if abs(S(s)S(s1))>precision goto step 1
This should converge faster
thanks for the thoughts guys; i really appreciate it!
felger carbon: the problem is not a tsp, as i know the order of the circles already (apologies for possibly not making this obvious earlier) and hence the 'rough' path through the circles i need to take. but you are right in that finding any path is trivial  i'd simply travel through each circle's centres in order!
arvo: interestingly i think i actually understand your maths! are you saying essentially (for "edit2") that you change the angle at one circle while examining the lengths coming either way off this point? please correct me if i am wrong.
one thing we know already is that for two points on the "outside" of a circle's tangent (i.e. a line joining them does not touch or cross the circle) the path representing the shortest distance has equal angles of incidence and reflection:
in the diagram, if you reflect B about the tangent, the shortest path between A and B is obviously a straight line, hence the equal angles theta. any other point on the line will yield a longer AB distance, and from the diagram it is also obvious that any point on the circle will yield a longer distance (except for the point on the tangent of course.)
given that we know this, i believe the challenge lies in defining the circle arc on which a point may lie (i.e. the bounds for R(n)), and getting a good estimate and effecting the above rule as many times as is necessary to get < precision.
felger carbon: the problem is not a tsp, as i know the order of the circles already (apologies for possibly not making this obvious earlier) and hence the 'rough' path through the circles i need to take. but you are right in that finding any path is trivial  i'd simply travel through each circle's centres in order!
arvo: interestingly i think i actually understand your maths! are you saying essentially (for "edit2") that you change the angle at one circle while examining the lengths coming either way off this point? please correct me if i am wrong.
one thing we know already is that for two points on the "outside" of a circle's tangent (i.e. a line joining them does not touch or cross the circle) the path representing the shortest distance has equal angles of incidence and reflection:
in the diagram, if you reflect B about the tangent, the shortest path between A and B is obviously a straight line, hence the equal angles theta. any other point on the line will yield a longer AB distance, and from the diagram it is also obvious that any point on the circle will yield a longer distance (except for the point on the tangent of course.)
given that we know this, i believe the challenge lies in defining the circle arc on which a point may lie (i.e. the bounds for R(n)), and getting a good estimate and effecting the above rule as many times as is necessary to get < precision.
You are right, this is what I meant.chylld wrote:arvo: interestingly i think i actually understand your maths! are you saying essentially (for "edit2") that you change the angle at one circle while examining the lengths coming either way off this point? please correct me if i am wrong.
One picture is worth more than thousand words:
As you can see, this algorithm handles both cases (line only touches circle or goes through it) without need to vary R(n). Red line corresponds to current optimal line placement, what you need to achieve by changing (currently increasing) A(n).
Your claim (the path representing the shortest distance has equal angles of incidence and reflection) is of course right, but completely irrelevant in my iterative algorithm.
Of course you can decrease computational cost by analyzing scene and splitting it to two cases  straight line intersects circle or not. But I think that computation time won't be too big anyway, even using my "brute force" approach.
Disclaimer.
I can't guarantee that my math is right or my algorithm gives any reasonable results. After all, I've not dealt with math problems for manymany years...
nice diagram arvo i think i finally understand your approach  rely on a totally forwardbased iteration/differentiation solution, rather than my method of trying to use a few rules/laws and building around those.
your method has a distinct advantage in that it will always satisfy the objective of having the path touch each circle in order. my approach involved the calculation of the 'arc' on each circle, and since each arc is more and more of an estimation compared to the last, posed the problem of missing a circle altogether during optimisation.
i'm not yet sure if it's possible to use differentiation to our advantage, but when i get to that stage i'll definitely try to use it (along with the 2nd derivative) to get some minimum points which will ease the burden of a purely iterative approach.
the only flaw i can see with your bruteforce approach is the case where in a sequence of circles A B and C, circles A and C lie entirely within circle B. the shortest path would hence be the shortest path straight from A to C, however the algorithm requires the path to touch the circumference of circle B and hence would result in an incorrect solution.
obviously an ideal would be to sample the whole area within each circle rather than just the circumference, but i have a feeling this is rather inefficient any thoughts on this?
your method has a distinct advantage in that it will always satisfy the objective of having the path touch each circle in order. my approach involved the calculation of the 'arc' on each circle, and since each arc is more and more of an estimation compared to the last, posed the problem of missing a circle altogether during optimisation.
i'm not yet sure if it's possible to use differentiation to our advantage, but when i get to that stage i'll definitely try to use it (along with the 2nd derivative) to get some minimum points which will ease the burden of a purely iterative approach.
the only flaw i can see with your bruteforce approach is the case where in a sequence of circles A B and C, circles A and C lie entirely within circle B. the shortest path would hence be the shortest path straight from A to C, however the algorithm requires the path to touch the circumference of circle B and hence would result in an incorrect solution.
obviously an ideal would be to sample the whole area within each circle rather than just the circumference, but i have a feeling this is rather inefficient any thoughts on this?
Da*n, you broke my nice universal algo (Like my everyday programming work  always some client finds hole in otherwise foolproof solution.)chylld wrote:the only flaw i can see with your bruteforce approach is the case where in a sequence of circles A B and C, circles A and C lie entirely within circle B. the shortest path would hence be the shortest path straight from A to C, however the algorithm requires the path to touch the circumference of circle B and hence would result in an incorrect solution.
Actually I assumed that circles do not overlap (exactly like coding  most problems arise from incorrect or misunderstood problem description). The latest case needs different formulas (like you said  iterate over the whole circle  or something equivalent); minimizing by two arguments (radius and angle  or some other pair of independent values) is somewhat more difficult.
I'll think about that in some later time
overlapping circles represent a case i also had not considered at first, but having just recently seen the data for which the algorithm will be used, it seems quite inevitable.
thankfully my brain is working this morning; a workaround to that is to not just consider the circumference of the current circle (i.e. varying An at the same Rn) but also the parts of the circumferences of other circles that lie within this circle.
assuming the differentiation doesn't prove too difficult, the hardest part would be to find the local minima on these arcs, as it might be hard to find stationary points.
but it should work
thankfully my brain is working this morning; a workaround to that is to not just consider the circumference of the current circle (i.e. varying An at the same Rn) but also the parts of the circumferences of other circles that lie within this circle.
assuming the differentiation doesn't prove too difficult, the hardest part would be to find the local minima on these arcs, as it might be hard to find stationary points.
but it should work