coordinates of points minimizing the infinity norm distance between two non-intersecting circles

Question

We are given two non-intersecting circles centered at $O_{1}$ and $O_{2}$. For simplicity sake, let $O_{1} = (0,0)$ and $r_{1} = r_{2} = 10$. Let $t$ be the distance between the two origins minus $2r$. In the picture, I call the distance between origins $deltaOrig$.

The circles do not overlap in either the x or y-dimensions.

In the attached image, $O_{2} = (27,23)$. Thus, as shown in the picture, $$t_{x} = (27-0-(2*10)) = 7 \\t_{y} = (23-0-(2*10) = 3$$.

To minimize the infinity norm or Chebyshev distance between the two circles, I need to find the point on each circle such that the quadrilateral between those two points is square with side length k.

How do I know this? I have this formulated as a QCP or quadratically constrained program optimization problem where I minimize the distance of the arc connecting the circles subject to each endpoint lying on a circle. Using this, I also find that the coordinates that minimize this distance form the angle $\theta$ as shown in the picture (pardon my imperfect drawing). For example in this instance, I find that $k = 11$ and the minimizing coordinates are $$(8,6)\\(19,17)$$.

Question: how do I find the geometric solution to this problem (what is $\theta$ as $O_2$ changes? I suspect there's a simple geometric argument but I am stumped except when the circles are distance enough that the square becomes a rectangle.

Here are some results from my CPLEX solution where $O_1$ remains $(0,0)$ and $r=10$: $O_2 = (50,30)$ then $k=30.0$ and $\theta = 0^{\circ}$
$O_2 = (49,30)$ then $k=29.024$ and $\theta = 2.798^{\circ}$
...
$O_2 = (30,30)$ then $k=15.857$ and $\theta = 45^{\circ}$
$O_2 = (29,30)$ then $k=15.367$ and $\theta = 47.026^{\circ}$
...
$O_2 = (11,30)$ then $k=10.024$ and $\theta = 87.202^{\circ}$
$O_2 = (10,30)$ then $k=10.0$ and $\theta = 90^{\circ}$

Thank you!

Answer 1

Calling

$$ \cases{ p_1 = (0,0)\\ p_2 = (27,23)\\ r_1 = 10\\ r_2 = 10\\ p=(x_1,y_1)\\ q=(x_2,y_2)\\ p_c=(y_1,x_2) } $$

we have the conditions

$$ \mathcal{R(x_1,y_1,x_2,y_2)}=\cases{ \|p-p_1\|^2=r_1^2\\ \|q-p_2\|^2=r_2^2\\ (p-p_c)\cdot(q-p_c) = 0\\ \|p-p_c\|^2=\|q-p_c\|^2 } $$

so the problem can be enunciated as

$$ \min_{x_1,x_2,y_1,y_2}\left(\|p-p_c\|^2+\|q-p_c\|^2\right),\ \ \text{s. t.}\ \ \mathcal{R}(x_1,y_1,x_2,y_2) $$

In our case we have

$$ \{ x_1 = 8, y_1 = 6, x_2 = 19, y_2 = 17 \} $$

Answer 2

So I came back to this a few days ago and have an answer for my own question.
As a reminder, a few assumptions:

• $r$ is the same for both circles. I do not try to generalize at all
• without loss of generality, both circles are translated so that one of them has an origin at (0,0)
• I use nomenclature from the original question posting plus the standard line definition $y=mx + b$ where $m$ is the slope and $b$ is the y-intercept
• the circles do not overlap since that trivial case has $k=0$
• there is surely an elegant proof from geometric arguments but that's beyond me. I observe a formula for calculating the length as a function of $O_2$

Observation 1: When $O_2$ lies on the line $x=y$, then because the 1-dimensional distance in x- and y-dimensions is the same, the line connecting the two optimal (x,y) points has slope $m=\pm1$ and y-intercept $b=0$. This is illustrated in the two images where $O_2 = (23,23)$ and $O_2 = (23,-23)$, respectively, $r=10$, $\theta=45^\text{o}$, and $k\approx8.857$ where $k$ is the length of square side meaning the out-and-back Chebyshev length is $2k\approx17.7$.

The case when the optimal points define a rectangle rather than a square is what I call the trivial case - I define it below.

Observation 2: As $O_2$ is moved away from the line $x=y$, the optimal points still define a square, so the line connecting the points still has $m=\pm1$ and $\theta_1=\theta_2$, but $b$ changes.
E.g. in these two images, $O_2 = (15,23)$ and $O_2 = (15,-23)$, respectively, $r=10$, and $k\approx5.447$ meaning the out-and-back Chebyshev length is $2k\approx10.87$. $\theta\approx28.5^\text{o}$ and the y-intercept of the optimal line is $b=\pm4$, respectively.

This suggests that to solve this without an optimization engine such as CPLEX, derive a formula for $b$ as a function of $O_2$ relative to $O_1=(0,0)$. From $b$, compute $p1$ and $p2$ as the intersections of the line and circles, and calculate $k$ from those points.

Observation 3: As $O_2$ moves sufficiently far off the line $x=y$, the optimal $\theta$ maxes out at $90^\text{o}$. Continue moving $O_2$ in that direction, $\theta$ remains $90^\text{o}$, and the optimal points no longer fall on a line of slope $m=\pm$. I show only one case here where $O_2 = (43,23)$ moves to $O_2 = (53,23)$. In each case, $\theta=90^\text{o}$ and the polygon connecting the points becomes a rectangle. $k$ increases from 23 to 33.

I call these the trivial cases and do not discuss further though you can see that identifying cases like this is a function of $2r$ and $|\delta_x|$ versus $|\delta_y|$ where $\delta_x=O_{2,x}-O_{1,x}=O_{2,x}$ and $\delta_y$ defined similarly, given our assumption that $O_1=(0,0)$. The other trivial case is when the circles intersect since the optimal Chebyshev distance is 0.

So how do we calculate $b$ as a function of $O_2$?

Let $\text{sign}(y) = +1$ if $y\ge0$ and -1 otherwise.

1. If $\delta_x \ge \delta_y$, then $b = \delta_y\cdot\frac{\text{sign}(O_{2,y})}{2}$.
2. Otherwise, $b = -\delta_y\cdot\frac{\text{sign}(O_{2,y})}{2}$.
3. Calculate the up-to-4 line-and-circle intersections and choose $p1$ and $p2$. From these, derive $k$ and $\theta$.

Because this produces a line where $m=\pm1$ we have a square (meaning Chebyshev distance is minimized given that x-dimension and y-dimension values are equal). And because the angle $\theta$ is the same, we have the best square since $k$ is minimized. Otherwise, if $\theta_1 \ne \theta_2$ then $\exists$ a $\theta$ such that $k$ is shorter.

Note that this formula is independent of $r$. The formula does not work when $r_1 \ne r_2$ but as I noted in the assumptions, I do not care about that case for this very limited-in-scope question.

Finally, why does this formula produce equal $\theta$? I do not have a proof. I am sure there is an argument one of you could point me to from 7th-grade geometry that would enable a legitimate proof here, but I never claimed to be a good mathematician.