hide
Free keywords:
-
Abstract:
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 is 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 Jacobi
curve, we are able to find non-singular tangential intersections. 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.
