Skip to Main content Skip to Navigation
Journal articles

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
Complete list of metadata

Cited literature [20 references]  Display  Hide  Download
Contributor : Sylvain Lazard Connect in order to contact the contributor
Submitted on : Thursday, September 29, 2005 - 5:59:52 PM
Last modification on : Thursday, January 20, 2022 - 4:16:33 PM
Long-term archiving on: : Thursday, April 1, 2010 - 10:35:16 PM




Sylvain Lazard, Luis Peñaranda, Sylvain Petitjean. Intersecting Quadrics: An Efficient and Exact Implementation. Computational Geometry, Elsevier, 2006, 35 (1-2), pp.74--99. ⟨10.1016/j.comgeo.2005.10.004⟩. ⟨inria-00000380⟩



Record views


Files downloads