EFFICIENT POLYNOMIAL ROOT ISOLATION APPLIED TO COMPUTATIONAL GEOMETRY

Abstract

Over the last several years, the field of polynomial root isolation has been rapidly improving, but the computational geometry applications have been somewhat unexplored. Here, we have an implementation of a curve intersection engine that showcases the current state-of-the-art in root isolation. The engine is capable of taking two implicitly defined curves and locating their intersection points within some required accuracy. From this work, we can clearly see that root isolation is no longer a significant speed issue in computational geometry. The next issue is really speed of the resultant computation used for variable elimination