On the computation of an arrangement of quadrics in 3D

In this paper, we study a sweeping algorithm for computing the arrangement of a set of quadrics in R3. We define a “trapezoidal” decomposition in the sweeping plane, and we study the evolution of this subdivision during the sweep. A key point of this algorithm is the manipulation of algebraic numbers. In this perspective, we put a large emphasis on the use of algebraic tools, needed to compute the arrangement, including Sturm sequences and Rational Univariate Representation of the roots of a multivariate polynomial system.