Solve that without 4th order polynomial?

[Gerenuk]

I was trying to calculate when two ellipses of the form ((x-x0)/a)^2+((y-y0)/b)^2=1 have intersections. Most of the time I get 4th order equations. Actually I only want to know a condition IF they just touch. Any ideas on this?

After playing around I had various equations. For example the problem is equivalent to finding beta in
$$\Re\left((\exp(i\beta)+z)^2\right)=b$$
where z is complex. Suggestions?

 

[tiny-tim]

Hi Gerenuk!

I don't know whether this will work, but have you tried simplifying it by squashing one of the coordinate axes so that one of the ellipses is a circle?

 

[Gerenuk]

Yes, I started like this too. Yet I haven't managed to avoid the 4th order equation. I tried setting the discriminant to zero to determine if the ellipses touch, but there were just too many terms, and I could find an easy way to factorize.
The above equation looks the simplest I could find. Yet not sure how to proceed.

 

[fzero]

The intersection of two generic conics will always be equivalent to solving the quartic, essentially due to Bezout's theorem. The best that you can do is reduce this to solving a cubic using some algebraic geometry techniques. The method is described in the context of conics at http://en.wikipedia.org/wiki/Conic_section#Intersecting_two_conics and in the context of the quartic at http://en.wikipedia.org/wiki/Quartic_equation#Algebraic_geometry

With two ellipses, it seems like we can simplify things quite a bit. Use linear transformations to map one of the ellipses to a unit circle. This transforms the parameters of the other ellipse, but it's still of the same form that you wrote down before. Let the center of this ellipse be $$(x_0',y_0')$$. Now since the unit circle is invariant under rotations in the plane, we can use a rotation to set, say, $$y_0'=0$$. But then the quartic equation for the intersection points is actually a perfect square so the problem reduces to solving a quadratic equation. The four points of intersection are $$(r_{\pm}, \pm \sqrt{1-r_\pm^2})$$, where $$r_\pm$$ are the roots to the quadratic.

For the ellipses to only touch, these four points must be coincident. This can only be the case if $$r_+=r_- = \pm 1$$. This requires the discriminant of the quadratic to vanish as well as a condition on the ratio of coefficients.

There's a certain amount of work to do to compute the coefficients of the quadratic above in terms of the parameters of the original ellipsi, but it doesn't seem too bad.

 

[Gerenuk]

Now since the unit circle is invariant under rotations in the plane, we can use a rotation to set, say, $$y_0'=0$$. But then the quartic equation for the intersection points is actually a perfect square so the problem reduces to solving a quadratic equation.

Hmm? How does that work? The ellipse is rotated so the equation still looks complicating?!

 

[fzero]

Hmm? How does that work? The ellipse is rotated so the equation still looks complicating?!

After transforming the first the ellipse into a unit circle ($$x=\cost t, y=\sin t$$), the equation for the points of intersection is

$$\frac{(\cos t -x_0')^2}{(a')^2} + \frac{(\sin t-y_0')^2}{(b')^2} = 1.$$

After a rotation with $$\tan\theta = y_0'/x_0'$$, this is put into the form

$$\frac{(\cos(t-\theta)-x_0'')^2}{(a')^2} + \frac{\sin^2(t-\theta)}{(b')^2} = 1,~~(*)$$

where

$$x_0''=x_0'\sqrt{ 1+ \left(\frac{y_0'}{x_0'}\right)^2}.$$

The whole point is that (*) is a quadratic equation for $$cos(t-\theta)$$.

 

[Gerenuk]

Hmm, actually this is incorrect. Rotating about the origin does not correspond to subtracting an angle from t.

To clarify, I tried plugging in t=a+b and finding an equation for b such that only cos(a) and cos^2(a) terms remain. However, this is not possible for general coefficients.

 

[tiny-tim]

Yet I haven't managed to avoid the 4th order equation.

You can't beat the system!

 

[fzero]

Hmm, actually this is incorrect. Rotating about the origin does not correspond to subtracting an angle from t.

Of course it does. The rotation matrix is

$$\begin{pmatrix} \cos\theta & \sin\theta \\ - \sin\theta & \cos\theta \end{pmatrix}$$

and it acts on

$$\begin{pmatrix} x \\ y \end{pmatrix} = \begin{pmatrix} \cos t \\ \sin t \end{pmatrix} .$$

You can verify the action on $$t$$. Remember that we have a unit circle based at the origin. What other action would a rotation around the origin have?

To clarify, I tried plugging in t=a+b and finding an equation for b such that only cos(a) and cos^2(a) terms remain. However, this is not possible for general coefficients.

I think the problem you're having is that the center of the 2nd ellipse is not invariant under this transformation.

I just tested my formula for 2 cases. The first was the unit circle and the circle $$(x-1)^2 + (y-1)^2 =1$$, which intersect at two points. The second was the unit circle and the circle $$(x-1)^2 + (y-1)^2 =(1-\sqrt{2}/2)^2,$$ which touch at a point.

You should try to convince yourself that the problem simplifies drastically if either $$x_0'$$ or $$y_0'$$ are zero. The rotation I made was a simple way to achieve this.

 

[Gerenuk]

You can't beat the system!

Actually I don't need the intersections, but I rather only want to know if there are any. So maybe there is a way to solve it.

@fzero:
If you just plug in this transformation, you don't get rid of y_0.
As I said, if you do it purely algebraically by setting t=a+b and trying to pick b as to eliminate sin(a) terms, you find it's impossible unless you are dealing with two circles on a diagonal.
So you incidently managed to pick exactly the two special cases where it works :) Tests should be more arbitrary.