3
$\begingroup$

My requirement is to find the point closest to three circles. So lets say the three circles are C1, C2, C3. I want to find the point in the space such that the SUM of its distance from C1, C2 and C3 is MINIMUM.

The distance of a given point from a circle is the distance of the given point from the point that lies on the circle and is intersection of the circle with the line joining the given point with the center of the circle.

I am okay to have the solution in Integer domain, which is where I need your help. I understand the problem can be tackled in Real domain by finding partial derivatives on X, Y axes: See the question in this link: https://math.stackexchange.com/questions/710547/solving-multivariate-polynomial-to-find-closest-point-to-a-3-or-more-circles

However I realised that solving the multivariate equations is not easy, and also time taking.

I'm not sure if trying to solve it in Integer domain will make the solution simpler and faster. I'm open to thoughts, and even if there are some approximations which will speed up the algo, I would be glad to listen to them.

Improve this question
$\endgroup$
13
  • $\begingroup$ I didn't look at this in detail, but would try the following, for the real problem: As in soap bubbles, I suspect it is where the lines to the circle centres meet at 120 degrees (this can be confirmed/refuted by differentiation). Find the equation of the locus of points at which the centres of two circles subtend 120 degrees. Then the desired point is the intersection of these three loci. $\endgroup$
    – user25199
    Commented Mar 20, 2014 at 9:25
  • $\begingroup$ Yes, one possible solution is the Fermat point. en.wikipedia.org/wiki/Fermat_point There are a lot of other cases. Sometimes the solution is on one of the circles. Sometimes it is a sort of anti-Fermat point. $\endgroup$
    – Douglas Zare
    Commented Mar 20, 2014 at 9:28
  • $\begingroup$ @Carl/Douglas: Most of the times the circles could intersect, which means the Fermat point may not be what I'm looking for. Fermat point would make sense only when the intersection does not happen between circles. $\endgroup$
    – user3098199
    Commented Mar 20, 2014 at 9:42
  • $\begingroup$ No, there are times when the Fermat point is optimal even though the circles intersect. There are times when the circles don't intersect, but the Fermat point is not optimal. $\endgroup$
    – Douglas Zare
    Commented Mar 20, 2014 at 9:54
  • $\begingroup$ @DouglasZare Then are you saying the radius of the circles do not matter? I am sorry, but from what you are saying, it means only the coordinates of the circles matter, and not the radius. However, we can easily debate that change in radius can easily impact the closest point. $\endgroup$
    – user3098199
    Commented Mar 20, 2014 at 9:58

2 Answers 2

Reset to default
1
$\begingroup$

While Douglas's answer will give exact solutions, I would like to suggest two simpler numerical approaches.

1. It is clear that the minimum lies in the convex hull of the circles, and that if the sum of distances in the centre of a square of side length $h$ is $S$, its minimum in the square is at least $S-3h/\sqrt{2}$. Thus an algorithm consisting of choosing an initial point and $h$ covering the convex hull.

At each step:

(a) Divide the square into nine smaller squares by adding eight points around each point in the previous iteration. So, if the point is at $(x,y)$, the new points will be at $(x\pm h/3,y\pm h/3)$, $(x\pm h/3,y)$ and $(x,y\pm h/3)$.

(b) Divide $h$ by 3

(c) Compute the sum of distances for each new point, $S(x_i,y_i)$ and find the minimum over all points considered so far,

$S_{\rm min}=\min_iS(x_i,y_i)$

(d) Remove points where the sum of distances is more than $\frac{3h}{\sqrt{2}}$ above this minimum, ie any $i$ for which $S(x_i,y_i)>S_{\rm min}+\frac{3h}{\sqrt{2}}$.

This is guaranteed to converge to the correct minimum, and hopefully answers the integer aspect of the OP's question.

2. Still easier (but non-rigorous): Use an out-of-the-box multidimensional optimization algorithm, for example in mathematica Towards the bottom of that page, four algorithms are described briefly: Nelder-Mead, Differential evolution, Simulated annealing and Random search.

Improve this answer
$\endgroup$
9
  • $\begingroup$ thanks for your answers. I would like to understand the first approach that you mentioned further. You have me for most of the approach, except for "t each step, divide the square into nine smaller squares by adding eight points around each point in the previous iteration, divide h by 3, compute the sum of distances for each new point, and remove points more than 32√h/2 above the minimum" Can you please elaborate this line further? $\endgroup$
    – user3098199
    Commented Mar 21, 2014 at 9:31
  • $\begingroup$ @user3098199 Elaborated as requested... $\endgroup$
    – user25199
    Commented Mar 21, 2014 at 9:56
  • $\begingroup$ Thanks for elaborate edit! Can you provide link for approach 2 which has details of how to solve similar problems? In the link you provided, the details are very minimal, am having a hard time figuring out how its related to this problem $\endgroup$
    – user3098199
    Commented Mar 21, 2014 at 10:10
  • $\begingroup$ @user3098199 I added some text - you can easily code the problem in mathematica to use these in-built routines, or use the ideas to develop your own code. Of course nonlinear optimization is a hard problem, so it is rare that you can be sure of getting the global minimum. $\endgroup$
    – user25199
    Commented Mar 21, 2014 at 10:23
  • $\begingroup$ (I used Mathematica to create the example below.) $\endgroup$
    – Joseph O'Rourke
    Commented Mar 21, 2014 at 10:57
2
$\begingroup$

An example: $C_1=[(0,0),1]\;,C_2=[(1,0),\frac{4}{5}]\;,C_3=[(2,\frac{3}{2}),\frac{3}{4}]\;.$

Contours show equal distance sums. $d_{\min}=\frac{3}{4}$ is achieved at $p_{\min} \approx (1.06, 0.80)$.

            ThreeCirclesFermat

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .