Talk:Problem of Apollonius

Suggest inline/block quoting the problem and algebraic solutions. (With citations, of course) --Michael Mol 17:34, 13 August 2010 (UTC)

Meta error propagation

Here's the danger of everyone copying everyone else's code: how many of the examples can handle the following three circles? x=0, y=2, r=1; x=0, y=-2, r=1; x=4, y=0, r=1 --Ledrug 23:38, 14 September 2011 (UTC)

OK great. What do we do to fix it? --Mwn3d 01:46, 15 September 2011 (UTC)

Problems which are simple translations are usually indications that the translator is unfamiliar with the algorithm and/or the target language. Perhaps rewrites (or audits) should be preferred. Perhaps translations should show up on the unimpl pages as ENAs? --Michael Mol 02:20, 15 September 2011 (UTC)

The problem is a division by zero, specifically when v11 is 0. AFAIK it's in all the examples. There may be other problems, for instance I wouldn't be surprised if all the solutions fail to handle some degenerate cases.

On a not quite related note, I do think line-by-line translations should be discouraged. Even if you have to pick up the algorithm from some existing examples, it's probably better to rewrite the code from semi-scratch, if only to make sure it's more idiomatic to your language. As to a solution -- I have no idea. --Ledrug 02:34, 15 September 2011 (UTC)

In searching of a proper fix, I scribbled many circles on a piece of paper, and reached the conclusion: I don't want any part of it. First off, the current problem of dividing by zero is just a minor annoyance. There are two fundamental problems:

1. Circles can't always be represented by [(x, y), r]. Even if we ignore degenerate input circles, one still has to deal with degenerate solution circles, e.g. [(0, -2), 1], [(0, 0), 1], [(0, 2), 1] has two solutions that are straight lines.
2. Touching each circle internally or externally isn't enough to identify a unique solution. [(0, -3), 2], [(0, 0), 1], [(0, 3), 2] has no solution that contains all circles inside, but has two solutions that's outside every circle. Essentially this involves whether solution is allowed to have negative radius: if it is, there's the risk of double counting; if not, there's the risk of missing solutions.

Besides the above, there are other special cases: [(0, 0), 1], [(0, 0), 2], [(0, 0), 3] has no solution; [(0, 1), 1], [(0, 2), 2], [(0, 3), 3] has infinitely many solutions, to name just two. Someone once said, "programming is all about special cases." Unfortunately, for Problem of Apollonius, there seem to be nothing but special cases. --Ledrug

For what it's worth: the J implementation treats all these degenerate cases as having no solutions. --Rdm 20:11, 15 September 2011 (UTC)

Wait, not even for [(0, -3), 2], [(0, 0), 1], [(0, 3), 2]? --20:29, 15 September 2011 (UTC)

Yes. For that case, it starts at the 0,-3 point (which is the center of the first circle), finds that the excess volume is negative infinity, and so stops there. But the error for 0,-3 is 112 which is larger than the acceptable error volume. So it reports no result. I suppose the question is: what criteria should be used to determine when simplex has completed, if it's not the presence of excess volume? Alternatively, what value should be reported for this case? And, why? --Rdm 20:54, 15 September 2011 (UTC)

I don't quite understand your question... assuming it's about solutions of the three circles, two of them are [(-4, 0), 3], [(4, 0), 3]. --Ledrug 21:04, 15 September 2011 (UTC)