Univariate Algebraic Kernel and Application to Arrangements

Sylvain Lazard 1, * Luis Peñaranda 1, * Elias Tsigaridas 2, *
* Corresponding author
1 VEGAS - Effective Geometric Algorithms for Surfaces and Visibility
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
2 GALAAD - Geometry, algebra, algorithms
CRISAM - Inria Sophia Antipolis - Méditerranée , UNS - Université Nice Sophia Antipolis, CNRS - Centre National de la Recherche Scientifique : UMR6621
Abstract : Solving polynomials and performing operations with real algebraic numbers are critical issues in geometric computing, in particular when dealing with curved objects. Moreover, the real roots need to be computed in a certified way in order to avoid possible inconsistency in geometric algorithms. Developing efficient solutions for this problem is thus an important issue for the development of libraries of computational geometry algorithms and, in particular, for the state-of-the-art (open source) cgal library. We present a cgal-based univariate algebraic kernel, which provides certified real-root isolation of univariate polynomials with integer coefficients and standard functionalities such as basic arithmetic operations, greatest common divisor (gcd) and square-free factorization, as well as comparison and sign evaluations of real algebraic numbers. We compare our kernel with other comparable kernels, demonstrating the efficiency of our approach. Our experiments are performed on large data sets including polynomials of high degree (up to 2 000) and with very large coefficients (up to 25 000 bits per coefficient). We also address the problem of computing arrangements of x-monotone polynomial curves. We apply our kernel to this problem and demonstrate its efficiency compared to previous solutions available in cgal. We also present the first bit-complexity analysis of the standard sweep-line algorithm for this problem.
Document type :
Reports
[Research Report] RR-6893, INRIA. 2009, pp.17
Liste complète des métadonnées

Cited literature [1 references]  Display  Hide  Download

https://hal.inria.fr/inria-00372234
Contributor : Luis Peñaranda <>
Submitted on : Tuesday, March 31, 2009 - 4:17:40 PM
Last modification on : Thursday, January 11, 2018 - 3:57:48 PM
Document(s) archivé(s) le : Thursday, June 10, 2010 - 7:25:54 PM

Files

RR-6893.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00372234, version 1

Citation

Sylvain Lazard, Luis Peñaranda, Elias Tsigaridas. Univariate Algebraic Kernel and Application to Arrangements. [Research Report] RR-6893, INRIA. 2009, pp.17. 〈inria-00372234〉

Share

Metrics

Record views

627

Files downloads

249