HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

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

Laurent Dupont 1 Michael Hemmer Sylvain Petitjean 1 Elmar Schomer
1 VEGAS - Effective Geometric Algorithms for Surfaces and Visibility
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : 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.
Document type :
Conference papers
Complete list of metadata

Contributor : Laurent Dupont Connect in order to contact the contributor
Submitted on : Friday, July 27, 2007 - 10:06:51 AM
Last modification on : Friday, February 26, 2021 - 3:28:08 PM

Links full text




Laurent Dupont, Michael Hemmer, Sylvain Petitjean, Elmar Schomer. Complete, Exact and Efficient Implementation for Computing the Adjacency Graph of an Arrangement of Quadrics. 15th Annual European Symposium on Algorithms - ESA 2007, Yossi Azar, Tel-Aviv U. and Microsoft Research uy Even, Tel-Aviv U. Amos Fiat, Tel-Aviv U. (Chair) Seffi Naor, Technion and Microsoft Research, Oct 2007, Eilat, Israel, October 8-10, 2007, Israel. pp.633-644, ⟨10.1007/978-3-540-75520-3_56⟩. ⟨inria-00165663⟩



Record views