Fast way to check if two curves intersect?

Question

Say I had $y = 2x^2 + 4x - 3$ and $4 = x^2 + y^2$ and I wanted to know whether they intersected. I could simultaneously solve them, but that takes time. Is there a faster way of checking if two curves intersected, if I don't care about where the intersection is itself?

Answer 1

The absolute fastest way? Suppose you are working over the complex field with points added at infinity. That is we stipulate that parallel lines actually intersect far out into the horizon (we say the line at infinity) similar to the way train track appear to the human eye. We call this projective geometry (Richard Souther has a visually epic account on youtube). Then by Bezout's theorem any two polynomials always intersect in either infinitely many points or in the product of their degrees counting multiplicity of roots. In this case they intersect in 4 points. Intersection becomes almost tautological (true by definition). In fact a form of Bezout holds for real space. It states that 2 polynomials intersect in at most the product of their degree points given they aren't the same polynomial. Here your parabola has degree 2 and your circle degree 2 so we know there can only be a maximum of 2x2=4 intersections. One sees there are less.

If you wanna be ${\rm I\!R}$eal though the fastest way (as C Marley said) is certainly graphically/intuitively. In this case your polynomials have exactly 2 intersections. 2nd degree equations in 2 variables are completely classified (they're all just intersections of a plane with a cone the so called conic sections (parabola, hyperbola, ellipse, circle)) so that you can always graph them relatively easily by completing the square to put them into standard forms. Higher degrees are much trickier not only geometrically but algebraically. Even this case results in a degree 4 polynomial which can seem impossible to solve exactly if it isn't in a nice easily factorable form although it still is plausible. There in fact is a cubic and a quartic equation similar to the quadratic equation! Although they are awfully long... Anything degree 5 or higher however doesn't have an equation similar to 2nd,3rd, and 4th degree polynomials and you'll need symmetric polynomials, permutations groups, automorphisms of field extensions, and much more a la Galois theory to determine if you can even theoretically solve it using the algebraic tools taught in HS (addition, subtraction, multiplication, division, and radicals).

The reality is the question you are asking is something that has been studied for millennium. It has greatly evolved over time and still grows to this day exponentially (if not factorially!) in the field of Algebraic Geometry. From humble Greek Euclidean beginnings on cones, to Rene Descarte's introduction of coordinates into geometry (the reason you can even write a geometric figure using algebra) to the modern day abstract algebra allowing us to study infinitely many different algebraic structures all at once, it is clear that the answer to your question is one that is highly non trivial. Algebraic Geometers were obsessed with precisely the question you asked, hence why they work in certain kinds of geometries to make polynomials behave nicely with such theorems as Bezout. What's so beautiful about the field is that the study of zeros of polynomial leads us to an understanding of all geometries as one further abstracts the very ideas that lead one to represent geometry through algebra. The breathtaking unity, elegance, and truth of Algebraic geometry and mathematics in general lead one to believe they are exploring the very thoughts of God that we mere humans spend lifetimes struggling to mine so we can grasp an infinitesimal fraction of infinity.

Answer 2

Generally speaking, there is no easy way to check that two curves intersect (even algebraic ones).

Here possible approach is to eliminate one of the variables to obtain a univariate polynomial. Then there are theorems about the approximate location of real roots.

In the case at hand, plugging $y$ in the second equation yields:

$$4x^4+16x^3+5x^2-24x+5=0.$$

The number of real roots can be settled by means of the Sturm Sequences.

Answer 3

Bolzano's Theorem, all the way.

The fastest way to see if two continuous curves, say, $f(x), g(x)$ intersect is to look at the function $h(x) = f(x) - g(x)$. Over some finite interval, say, $x \in [a,b]$, evaluate $h$ at both endpoints i.e. $h(a), h(b)$ and see if it changes signs i.e. $h(a)h(b) < 0$. Then, by Bolzano's theorem, we have that $h(x) = 0$, for at least one $x \in [a,b]$. This implies $h(x) = 0 \implies f(x) - g(x) = 0 \implies f(x) = g(x)$ for some $x$.