Talk:Problem of Apollonius: Difference between revisions

Content added Content deleted

Inline

Revision as of 19:12, 15 September 2011

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:

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.
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

@@ Line 8: / Line 8: @@
 ::: 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. --[[User:Ledrug|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:
+# Circles can't always be represented by <code>[(x, y), r]</code>. Even if we ignore [[wp:Special cases of Apollonius' problem|degenerate input circles]], one still has to deal with degenerate solution circles, e.g. <code>[(0, -2), 1], [(0, 0), 1], [(0, 2), 1]</code> has two solutions that are straight lines.
+# Touching each circle internally or externally isn't enough to identify a unique solution. <code>[(0, -3), 2], [(0, 0), 1], [(0, 3), 2]</code> 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: <code>[(0, 0), 1], [(0, 0), 2], [(0, 0), 3]</code> has no solution; <code>[(0, 1), 1], [(0, 2), 2], [(0, 3), 3]</code> 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. --[[User:Ledrug|Ledrug]]