6533b826fe1ef96bd128466b

RESEARCH PRODUCT

Complete, Exact and Efficient Implementation for Computing the Adjacency Graph of an Arrangement of Quadrics

subject

description

The original publication is available at www.springerlink.com ; ISBN 978-3-540-75519-7 ; ISSN 0302-9743 (Print) 1611-3349 (Online); International audience; We present a complete, exact and efficient implementation to compute the adjacency graph of an arrangement of quadrics, \ie surfaces of algebraic degree~2. This is a major step towards the computation of the full 3D arrangement. We enhanced an implementation for an exact parameterization of the intersection curves of two quadrics, such that we can compute the exact parameter value for intersection points and from that the adjacency graph of the arrangement. Our implementation is {\em complete} in the sense that it can handle all kinds of inputs including all degenerate ones, \ie singularities or tangential intersection points. It is {\em exact} in that it always computes the mathematically correct result. It is {\em efficient} measured in running times, \ie it compares favorably to the only previous implementation.