# Item

ITEM ACTIONSEXPORT

Released

Conference Paper

#### Computing a 3-dimensional Cell in an Arrangement of Quadrics: Exactly and Actually!

##### MPS-Authors

##### Locator

There are no locators available

##### Fulltext (public)

There are no public fulltexts available

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Geismann, N., Hemmer, M., & Schömer, E. (2001). Computing a 3-dimensional Cell
in an Arrangement of Quadrics: Exactly and Actually! In *Proceedings of the 17th Annual Symposium on
Computational Geometry (SCG-01)* (pp. 264-273). New York: ACM.

Cite as: http://hdl.handle.net/11858/00-001M-0000-000F-317E-3

##### Abstract

We present two approaches to the problem of calculating a cell in a
3-dimensional arrangement of quadrics. The first approach solves the
problem using rational arithmetic. It works with reductions to
planar arrangements of algebraic curves. Degenerate
situations such as tangential intersections and self-intersections of
curves are intrinsic to the planar arrangements we obtain.
The coordinates of the intersection points are given by
the roots of univariate polynomials.
We succeed in locating all intersection points either by extended
local box hit counting arguments or by globally characterizing
them with simple square root expressions.
The latter is realized by a clever factorization of the univariate
polynomials. Only the combination of these two results
facilitates a practical and implementable algorithm.
The second approach operates directly in 3-space by applying
classical solid modeling techniques. Whereas the first
approach guarantees a correct solution in every case the second one
may fail in some degenerate situations. But with the
help of verified floating point arithmetic it can detect these
critical cases and is faster if the quadrics are in general
position.