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)