Wolpert, Nicola

An Exact and Efficient Approach for Computing a Cell in an Arrangement of Quadrics

In this thesis, we present an approach for the exact and efficient
computation of a cell in an arrangement of quadric surfaces. All
calculations are based on exact rational algebraic methods and provide
the correct mathematical results in all, even degenerate, cases. By
projection, the spatial problem can be reduced to the one of computing
planar arrangements of algebraic curves. We succeed in locating all
event points in these arrangements, including tangential intersections
and singular points. By introducing an additional curve, which we call
the {\em Jacobi curve}, we are able to find non-singular tangential
intersections. By a generalization of the Jacobi curve we are able to
determine non-singular tangential intersections in arbitrary planar
arrangements. We show that the coordinates of the singular points in
our special projected planar arrangements are roots of quadratic
polynomials. The coefficients of these polynomials are usually
rational and contain at most a single square root. A prototypical
implementation indicates that our approach leads to good performance in
practice.