Continued Work on the Computation of an Exact Arrangement of Quadrics
Michael Hemmer, Sebastian Limbach, Elmar Schömer · Max Planck Institute for Plasma Physics · 2009
We present an exact and complete algorithm for the computation of all edge cycles bounding the faces of a three-dimensional arrangement of algebraic surfaces of degree two (quadrics). The algorithm is based on the implementation by Hemmer et al. [9] which computes the adjacency graph of the arrangement. However, this graph is just the set of vertices and their connectivity along the edges. We enhance each vertex of the graph by a description of its local neighborhood in a so-called environment map, which finally enables the initialization of all edge cycles in the arrangement. This is a major step towards the computation of the full arrangement. The implementation is complete up to a few special cases, and covers several variants in order to compute the environment map.