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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [2 references]  Display  Hide  Download

https://hal.inria.fr/inria-00336563
Contributor : Sylvain Lazard <>
Submitted on : Tuesday, November 4, 2008 - 2:48:47 PM
Last modification on : Thursday, January 11, 2018 - 6:20:14 AM
Long-term archiving on : Tuesday, October 9, 2012 - 3:00:31 PM

File

univ_esa08.pdf
Files produced by the author(s)

Identifiers

  • 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. ⟨inria-00336563⟩

Share

Metrics

Record views

395

Files downloads

131