# Software of the team

## CGAL

We are participating in the development of CGAL, the Computational Geometry Algorithms Library.

Together with our partners, we developed the following packages:

- 2D Triangulations on the Sphere
- 2D Hyperbolic Delaunay Triangulations
- 2D Periodic Hyperbolic Triangulations
- 3D Periodic Mesh Generation

**NEWS**: CGAL RECEIVES A TEST OF TIME AWARD AT SOCG 2023

## QI

QI stands for Quadrics Intersection. QI is the first exact, robust and efficient implementation of an algorithm for parameterizing the intersection of two arbitrary quadrics given in implicit form. QI computes an exact parameterization of the intersection of two quadrics with integer coefficients of arbitrary size with the following features:

- QI identifies, separates and parameterizes all the algebraic components (lines, conics, cubic, quartic) of the intersection;
- the parameterization is rational when one exists; otherwise the intersection is a non-singular quartic and the parameterization involves the square root of a polynomial;
- the coefficients of parameterization are small in the sense that the degree of the field extension (over the rationals) on which they are defined is minimal except in a small number of cases in which they may involve one extra possibly unnecessary square root;
- QI is fast and efficient and can routinely compute parameterizations of the intersection of quadrics with input coefficients having ten digits in less than 50 milliseconds on a mainstream PC.

## ISOTOP

Isotop is a Maple software for computing the topology/isotopy of an implicit algebraic plane curve, that is, for computing an arrangement of polylines isotopic to the input curve. It also provides a new solution to the important problem of plotting such curves in a certified way, that is -- in particular -- without missing connected components, singular points, etc. This problem is also a necessary key step for computing arrangements of algebraic curves. Isotop is based on the algorithms we developped in a series of paper.

See the Online server.

## Complex root solving

Based on recent and classical work on polynomial solving, we implemented several software libraries to find the complex roots of univariate polynomial equations:

## Subdivision solver

For drawing curves and surfaces defined by high degree polynomial equations, we developed and implemented algorithms combining subdivision with multipoint evaluation approaches.