8
$\begingroup$

In the famous "Problem of Apollonius" (https://en.wikipedia.org/wiki/Problem_of_Apollonius), the goal is to draw three circles that are tangential to another circle:

enter image description here

Algebraically, we can write this problem as a system of equations:

$$(x_s-x_1)^2+(y_s-y_1)^2=(r_s-s_1 r_1)^2$$ $$(x_s-x_2)^2+(y_s-y_2)^2=(r_s-s_2 r_2)^2$$ $$(x_s-x_3)^2+(y_s-y_3)^2=(r_s-s_3 r_3)^2$$

My Question: Can we consider this above problem as a "constraint optimization problem"?

For instance, from the above equations:

  • we want to find out values of "x1, y1, s1, r1, x2, y2, s2, r2, x3, y3, s3, r3"
  • such that all "black circles" intersect with the "purple circle"

Thus: we could make a objective function

  • that takes inputs "x1, y1, s1, r1, x2, y2, s2, r2, x3, y3, s3, r3"

  • and that outputs a number between "0 and 1" corresponding to the proportion of "black circles" are tangential to the "purple circle" (e.g. 0, 0.33, 0.66, 0.99)

Thus, we could use some Optimization Algorithm such as the Genetic Algorithm for trying to generate "feasible combinations" of "x1, y1, s1, r1, x2, y2, s2, r2, x3, y3, s3, r3" such that "the proportion of black circles tangential to the purple circle" are optimized (hoping that we eventually get a value of 0.99, signifying that the Problem of Apollonius is solved).

Is this correct?

Note Does anyone know why the "Problem of Apollonius" was considered to be so difficult? Was the original objective of this problem to prove that circles can be drawn this way? Or was the original objective of this problem to prove that this can be done for more than 3 circles?

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ This is correct, you have variables and constraints, you are good ! you can use any dummy objective function. $\endgroup$
    – Kuifje
    Feb 10, 2022 at 17:16
  • 1
    $\begingroup$ You can checkout Erwin's blog with articles dealing with related problems : yetanothermathprogrammingconsultant.blogspot.com/2018/05/… . He uses non linear solvers (and not genetic algorithms). $\endgroup$
    – Kuifje
    Feb 10, 2022 at 17:21
  • 1
    $\begingroup$ The original question asked for a closed-form solution, not an approximation, such as a generic optimization algorithm would produce. $\endgroup$
    – TLW
    Feb 11, 2022 at 2:22
  • 7
    $\begingroup$ Please fix the problem statement. The goal is to draw one circle that is tangent to all three of the given circles, not the other way around. What you wrote is a trivial problem. $\endgroup$
    – quarague
    Feb 11, 2022 at 7:32
  • $\begingroup$ On “why it’s difficult”, this is explained in the Wikipedia article under the history section. Since the original solution by Apollonius was lost, and Euclidean Geometry ought to be solved with compass and ruler, it wasn’t until 1600 that a solution was found by François Viète. The method is explained in the article. $\endgroup$
    – Abel
    Feb 12, 2022 at 3:44

2 Answers 2

Reset to default
18
$\begingroup$

You have the inputs and outputs confused. The three black circles are given, and the purple circle is a desired output.

But, yes, any system of equations can be thought of as an optimization problem with a constant zero objective.

Another common approach is to modify the constraints by introducing nonnegative surplus and slack variables and then minimize their sum. If the resulting minimum is 0, you have a feasible solution to the original constraints. Otherwise, the problem is infeasible. In the two-phase simplex method for LP, this is Phase I.

Improve this answer
$\endgroup$
1
  • $\begingroup$ @ RobPratt: Thank you so much for your answer! Just a question: Do you know why the "Problem of Apollonius" is considered to be a difficult problem in general? In Microsoft Paint, I tried replicating these circles without much trouble imgur.com/a/zviHPx8 . Is there some particular reason why this problem is considered to be difficult? thank you so much! $\endgroup$
    – stats_noob
    Feb 10, 2022 at 17:28
5
$\begingroup$

Since I can't comment due to lack of reputation, here's an a note in response to your comment on RobPratt's answer: The difficulty is not so much in managing to draw something close to the desired circle in practice, but rather in the mathematical construction (using only straightedge and compass!).

This turns out to have some interesting mathematical implications - cf. e.g. doubling the square, doubling the cube (https://en.wikipedia.org/wiki/Doubling_the_cube), squaring the circle (https://en.wikipedia.org/wiki/Squaring_the_circle), ...

Note also that approximating a solution with Paint is not the same as determining a mechanism to obtain the new circle's midpoint and radius from the given ones.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ And in the same vein, although the problem can be set up in the form of a constraint optimization problem, per the OP's suggestion, that doesn't imply that tools and approaches commonly used for such problems would necessarily be appropriate for solving this one. For example, the OP raises a genetic algorithm as a possible approach, but it seems unlikely that solutions to this particular problem could be obtained by such an approach. $\endgroup$
    – John Bollinger
    Feb 11, 2022 at 16:37
  • $\begingroup$ @JohnBollinger: If the optimization problem is well-stated, there's no reason that genetic algorithms wouldn't work reasonably well. I actually see no need for constraints here at all. $\endgroup$
    – Ben Voigt
    Feb 11, 2022 at 18:37
  • 1
    $\begingroup$ Well that's just it, @BenVoigt. It can be put in the form of an optimization problem, but it isn't one in the usual sense. Certainly the OP's proposed metric is not suitable as written for a genetic algorithm, because it provides no useful signal for trial solutions that are close (in some sense) but not exact solutions. And I guess that comes around to an important point: computing an answer analytically is a different problem from estimating a solution by optimization methods. $\endgroup$
    – John Bollinger
    Feb 11, 2022 at 19:11
  • $\begingroup$ I'm quite sure this problem can be posed as a "nice" optimization problem, not unusual in any way. Agreed that the formulation in the question, aside from solving for the input instead of the outputs of the famous problem, is not an optimization problem, only a feasibility search, and thus optimization algorithms don't directly apply. But write a good objective function (e.g. minimize sum-of-squared-error across the desired equalities) and it becomes pretty nice. $\endgroup$
    – Ben Voigt
    Feb 11, 2022 at 20:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.