Geometric clipping methods for efficient root finding

Root-finding methods have wide applications in geometry computation. Typical examples include curve/surface intersection, surface rendering, collision detection, and bisectors/medial axes computation. This talk presents an overview of geometric clipping methods for efficient root-finding of a given polynomial or an arbitrary smooth function within an interval. The main idea of the methods is to use lower order polynomial curves for bounding the roots of a higher order polynomial or an arbitrary smooth function under certain conditions. The given function is locally approximated as a lower order polynomial curve based on sample positions and relevant tangent information. Two bounding polynomials, named clipping polynomials, are further produced for bounding the roots of the original function with a substantially reduced interval. For a quadratic polynomial curve used for clipping, e.g., an optimal convergence rate of 4 can be achieved for finding a single root. In case of a cubic clipping polynomial curve, an optimal convergence rate of 6 can be achieved for finding a single root.