Version 2.0 is out! šŸŽ‰ Check out the changelog to see what is new.

When do two ellipses meet?

Let two ellipses grow until they intersect

Let two ellipses be centered at points $p_1,p_2$: $$ E_i( r ) = \{x\in \mathbb{R}^2 \mid (x-p_i)^T Q_i^TQ_i(x-p_i) = r^2\}, i=1,2, $$ where $Q_1, Q_2$ are symmetric matrices.

We wish to find the smallest radius $r$ for which $E_1( r )\cap E_2( r )$ is not empty. Let $r^\star$ be the solution for this optimization problem. In Julia we translate this into a polynomial system:

using HomotopyContinuation, LinearAlgebra
# generate the variables
@polyvar Qā‚[1:2, 1:2] Qā‚‚[1:2, 1:2] pā‚[1:2] pā‚‚[1:2]
@polyvar x[1:2] r
zā‚ = x - pā‚
zā‚‚ = x - pā‚‚
# initialize the equations for Eā‚ and Eā‚‚
fā‚ = (Qā‚ * zā‚) ā‹… (Qā‚ * zā‚) - r^2
fā‚‚ = (Qā‚‚ * zā‚‚) ā‹… (Qā‚‚ * zā‚‚) - r^2
# initialize the equation for Eā‚ and Eā‚‚ being tangent
@polyvar Ī»
g = (Qā‚' * Qā‚) * zā‚ - Ī» .* (Qā‚‚' * Qā‚‚) * zā‚‚
# gather everything in one system
F = [fā‚; fā‚‚; g];

An initial solution is given by two circles, each of radius 1, centered at $(1,0)$ and $(-1,0)$, respectively. Let us track this solution to the system given by

$$p_1 = [3,0], p_2 = [1,2], Q_1 = \begin{pmatrix} 1 & 1\\ 1 & 0 \end{pmatrix}, Q_2 = \begin{pmatrix} 0 & 2 \\ 2 & 1 \end{pmatrix}.$$

That is, the parameters are $p_1, p_2, Q_1, Q_2$ and the variables are $x,r,Ī»$. Now we track the starting solution towards the target system

julia> params = [vec(Qā‚); vec(Qā‚‚); pā‚; pā‚‚]
julia> q = [1, 0, 0, 1, 1, 0, 0, 1, 1, 0, -1, 0]
julia> p = [vec([1 1; 1 0]); vec([0 2; 2 1]); [3, 0]; [1, 2]]
julia> solve(F, [[0, 0, 1, -1]], parameters=params, start_parameters=q, target_parameters=p)
Result with 1 solutions
==================================
ā€¢ 1 non-singular solution (1 real)
ā€¢ 0 singular solutions (0 real)
ā€¢ 1 paths tracked
ā€¢ random seed: 805680

The computation reveals that $r^\star \approx 1.317$. Here is a picture.

Cite this example:
@Misc{ ellipses-tangent2020 ,
    author =  { Paul Breiding },
    title = { When do two ellipses meet? },
    howpublished = { \url{ https://www.JuliaHomotopyContinuation.org/examples/ellipses-tangent/ } },
    note = { Accessed: July 13, 2020 }
}

Published by