A CGAL-based Univariate Algebraic Kernel and Application to Arrangements

Sylvain Lazard 1 Luis Peñaranda 1 Elias P. Tsigaridas 1
1 VEGAS - Effective Geometric Algorithms for Surfaces and Visibility
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : Solving univariate polynomials and operations with real algebraic numbers are critical in geometric computing with curved objects. Moreover, the real roots need to be computed in a certified way in order to avoid possible inconsistency in geometric algorithms. We present a CGAL-based univariate algebraic kernel, which follows the CGAL~specifications for univariate kernels. It provides certified real-root isolation of univariate polynomials with integer coefficients (based on the library \rs) and standard functionalities such as basic arithmetic operations, gcd and square-free factorization, as well as comparison and sign evaluations of real algebraic numbers. We compare our implementation with the univariate algebraic kernel developed at MPII, that also follows CGAL~specifications, on various data sets, using polynomials of degree up to 2 000 and maximum coefficient bit-size up to 25 000. Finally we apply our kernel to the computation of arrangements of univariate polynomial functions, and we present a bit complexity analysis of the algorithm for computing the arrangement of planar curves defined by univariate polynomials.
Type de document :
Communication dans un congrès
24th European Workshop on Computational Geometry - EuroCG 2008, Mar 2008, Nancy, France. pp.91--94, 2008
Liste complète des métadonnées

Littérature citée [2 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00336563
Contributeur : Sylvain Lazard <>
Soumis le : mardi 4 novembre 2008 - 14:48:47
Dernière modification le : mardi 25 octobre 2016 - 16:58:38
Document(s) archivé(s) le : mardi 9 octobre 2012 - 15:00:31

Fichier

univ_esa08.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00336563, version 1

Collections

Citation

Sylvain Lazard, Luis Peñaranda, Elias P. Tsigaridas. A CGAL-based Univariate Algebraic Kernel and Application to Arrangements. 24th European Workshop on Computational Geometry - EuroCG 2008, Mar 2008, Nancy, France. pp.91--94, 2008. 〈inria-00336563〉

Partager

Métriques

Consultations de la notice

228

Téléchargements de fichiers

104