Robustly and Efficiently Computing Algebraic Curves and Surfaces

Computing with curved geometric objects forms the basis for many algorithms in areas such as geometric modeling, computer aided design and robot motion planning. In general, such computations cannot be carried out reliably with standard machine precision arithmetic.

Slightly more than a decade ago robustly and efficiently dealing with conics and Bézier curves in 2D and quadrics and splines in 3D was considered an enormous challenge. This picture has changed. Our first successes were achieved for conics and quadrics, mainly relying on properties of the involved low-degree polynomials. In a second step, to tackle general algebraic curves and surfaces, we exploited more involved mathematical tools such as subresultants. In addition with clever filtering techniques, these methods already beat the previous specialized solutions. The most recent

drastical

success in performance gain for algebraic curves is due to several ingredients: The central one consists of a cylindrical algebraic decomposition with a revised lifting step. Using results from algebraic geometry we avoid any change of coordinates and replace the costly symbolic operations by numerical tools. The new algorithms for curve topology computation only need to compute the resultant and the gcd of bivariate polynomials and to perform numerical root finding. For the symbolic operations, we can rely on implementations exploiting graphics hardware, which is several magnitudes faster than corresponding CPU implementations.

All algorithms have been implemented as contributions to the C++! project

Cgal

. Excellent practical behavior of our algorithms has been shown in exhaustive sets of experiments, where we compared them with our previous and recent competing approaches. Beyond, the algorithms are also proven to be efficient in theory. Recent work shows that our implemented and practical algorithm needs

$\tilde{O}(d^6 + d^5\tau)$

bit operations (

d

degree,

τ

bitsize of coefficients) to compute the topology of an algebraic curve and for solving bivariate systems.

Joint work with Pavel Emeliyanenko, Michael Kerber, Kurt Mehlhorn, Michael Sagraloff, Alexander Kobel, and Pengming Wang.