Date: Sat, 2 Nov 96 01:47:30 CST
From: rusin (Dave Rusin)
To: presnell@alphasun.anu.edu.au
Subject: Re:  Intersecting ellipses

>As efficiently as possible, I need to be able to check whether (lots
>of) pairs of ellipses intersect.  The actual points of intersection
>are not of interest to me.  Your posting indicated that this could be
>done without solving for the roots, but I'm afraid I'm not familiar
>with some of the terminology.  You said
>
>  There are three polynomials one can form from the
>  coefficients of the quartic, one of which is the discriminant  D,
>  with the property that
>        there are two real roots iff  D<0
>        there are four real roots iff D>0 and the other two polynomials
>           are also positive.
>
>What exactly are these polynomials?  Is there a reference for this?
>By D<0, I assume you mean D(x) < 0 for all x.

You need the theory of Sturm sequences. They're treated in those wonderful
19th century books on the Theory of Equations in your library. Some
information is available online; for example I have some old posts:
	http://www.math.niu.edu/~rusin/known-math/96/sturm
	http://www.math.niu.edu/~rusin/known-math/94/sturm.seq
[URLs updated 1999/01 -- djr]
And no, I meant  D  is a constant which is computed from the coefficients
of the polynomial (e.g. for a quadratic it's the famous  b^2-4ac .)
One _can_ write functions of  x, and look at their sign changes for
various  x  to determine the number of real roots _in intervals_,
but it sounds like you don't need that refinement.

>I assume that using the discriminant (whatever it is) actually more
>efficient than finding the real zeros of its derivative and evaluating
>the quartic at those points?

Yes, certainly: this work can be done in exact arithmetic (assuming the
coefficients of the polynomial are known exactly), so for
example if the coefficients are integers there will never be any 
problem distinguishing "near misses" from real roots, since
(barring overflow) there is zero roundoff error in integer arithmetic.

dave