ROBUST INTERVAL ALGORITHM FOR CURVE INTERSECTIONS

In this paper, we develop and study a robust algorithm for computing i ntersections of two planar interval polynomial curves. The intersectio n problems include well-conditioned transveral intersections as well a s ill-conditioned cases such as tangential and overlapping intersectio ns. Key components of our methods are the reduction of the intersectio n problems into solving systems of nonlinear interval polynomial equat ions which consist of m equations with n unknowns. An earlier interval nonlinear polynomial solver for balanced system based on Bernstein su bdivision method coupled with rounded interval arithmetic is extended to solve unbalanced systems. The solver provides results with numerica l certainty and verifiability. Examples illustrate our techniques. Cop yright (C) 1996 Elsevier Science Ltd