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

Michael Hemmer 1 Laurent Dupont 2 Sylvain Petitjean 2 Elmar Schömer 3
1 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
2 VEGAS - Effective Geometric Algorithms for Surfaces and Visibility
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
3 Institut für Informatik / Institute of Computer Science [Mainz]
Abstract : We present a complete, exact and efficient implementation to compute the edge-adjacency graph of an arrangement of quadrics, i.e. 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 edge-adjacency graph of the arrangement. Our implementation is complete in the sense that it can handle all kinds of inputs including all degenerate ones, i.e. singularities or tangential intersection points. It is exact in that it always computes the mathematically correct result. It is efficient measured in running times, i.e. it compares favorably to the only previous implementation.
Keywords : Arrangement intersection of surfaces quadrics pencils of quadrics curve parameterization
Type de document :
Article dans une revue
Journal of Symbolic Computation, Elsevier, 2011, 46 (4), pp.467-494. <10.1016/j.jsc.2010.11.002>
Liste complète des métadonnées
https://hal.inria.fr/inria-00537592
Contributeur : Sylvain Petitjean <>
Soumis le : jeudi 18 novembre 2010 - 17:06:29
Dernière modification le : jeudi 9 février 2017 - 15:47:41

Identifiants

Collections

INRIA | LORIA | UNIV-LORRAINE

Citation

Michael Hemmer, Laurent Dupont, Sylvain Petitjean, Elmar Schömer. A Complete, Exact and Efficient Implementation for Computing the Edge-Adjacency Graph of an Arrangement of Quadrics. Journal of Symbolic Computation, Elsevier, 2011, 46 (4), pp.467-494. <10.1016/j.jsc.2010.11.002>. <inria-00537592>

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

395

Contact


archive-ouverte@inria.fr