Thanks for the input guys. To clear things up, I am interested in the root values, but not always. The circles intersecting my trajectory can either be obstacles to be avoided or waypoints to be followed. For the obstacles I just need to know if the obstacle is avoided. For the waypoint case I need to know if the waypoint is crossed, and if not, I want to know the Closest Point of Approach between the trajectory and the waypoint. You see I make some corrections to the polynomials based on the CPA to move them closer to the waypoints. If there is no intersection between the waypoint and the polynomials, then the complex root of the equation below will give the time of CPA and hence the CPA.

[EQN]
\sqrt{(x(t)-W_x )^2+(y(t)-W_y )^2} - r = 0
[/EQN]

I have already tried Sturm, and it works. It can also be used recursively to find the roots. It does require a lot of convolution and deconvolution though (polynomial multiplication and division) and gets quite time consuming quite quickly.

Another thing I’ve tried is Chebfun, which generates a polynomial expansion of a function. It can be used to find the roots of a polynomial of any degree. It’s not analytical but it’s quite accurate. Again the computation time is a higher than I would like.

For Sturm and Chebfun, I don’t think there is any great advantage in using them over numerical root finders for my particular problem. JeffreyTitan your quadratic suggestion looks interesting, I’ll plug some numbers in to see what I think. Otherwise I think I’ll do something similar to what Josh suggested and break my trajectory into lots of small linear segments. This should keep things fast and the loss of accuracy should be minimal.

Thanks for updating us on your progress, always good to hear how it goes. Keep in mind that my suggestion was invented on the spot and is a bound only. But I'd be curious to know if/how much it worked. I'm too busy with my own projects to test it out. ;)