Intersecting Quadrics: An Efficient and Exact Implementation

Sylvain Lazard 1 Luis Peñaranda 1 Sylvain Petitjean 1
1 VEGAS - Effective Geometric Algorithms for Surfaces and Visibility
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : We present the first complete, exact, and efficient C++ implementation for parameterizing the intersection of two implicit quadrics with integer coefficients of arbitrary size. It is based on the near-optimal algorithm recently introduced by Dupont et al. and builds upon Levin's seminal work. Unlike existing implementations, it correctly identifies and parameterizes all the connected components of the intersection in all cases, returning parameterizations with rational functions whenever such parameterizations exist. In addition, the coefficient rings of the parameterizations are either minimal or involve one possibly unneeded square root. We prove upper bounds on the size of the coefficients of the output parameterizations and compare these bounds to observed values. We give other experimental results and present some examples.
Document type :
Journal articles
Computational Geometry, Elsevier, 2006, 35 (1-2), pp.74--99
Liste complète des métadonnées
Contributor : Sylvain Lazard <>
Submitted on : Thursday, September 29, 2005 - 5:59:52 PM
Last modification on : Tuesday, December 13, 2016 - 3:41:10 PM
Document(s) archivé(s) le : Thursday, April 1, 2010 - 10:35:16 PM


  • HAL Id : inria-00000380, version 1



Sylvain Lazard, Luis Peñaranda, Sylvain Petitjean. Intersecting Quadrics: An Efficient and Exact Implementation. Computational Geometry, Elsevier, 2006, 35 (1-2), pp.74--99. <inria-00000380>



Record views


Document downloads