Finding intersections of algebraic curves in a convex region using encasement

We present a subdivision based technique for finding the intersections of two algebraic curves inside a convex region. Even though it avoids computing resultants, the technique is guaranteed to find all intersections with bounded backwards error. The subdivision, called an encasement, also encodes the arrangement structure of the curves. We implement the encasement algorithm using adaptive precision interval arithmetic. We compare its performance to the CGAL library implementation of resultant based curve intersection techniques. We provide CPU and CPU/GPU versions of the algorithm and implementation. On the CPU, encasement generates all curve intersections, to accuracy 10⁻⁸, 10 to 30 times faster than CGAL for degrees 8 to 18, and it handles degrees up to 20 that CGAL cannot handle. The GPU speeds up the calculation by a factor of 3 to 4.