# Curved Kernel

Monique Teillaud

Our overall goal is to extend to curved objects the definitions of the classical geometric structures and the algorithms to compute them.
 The goal is also implementation in the CGAL Library. Historically, the CGAL kernels provided the user mainly with linear objects (points, line segments, lines...) and predicates on them. Curves were present in the traits classes of certain specific packages: arrangement with a traits class for conic arcs, optimization with conics, Apollonius graph with circles. There is a need for a general kernel providing the user with - classes for curved objects - predicates and constructions on them. The effort consists first of all on defining general concepts. On the implementation side, a kernel for 2D circular arcs was first released in CGAL 3.2 and a kernel for 3D circular arcs was released in CGAL 3.4. The curved kernel is parameterized by a BasicKernel parameter and derives from it, in order to include all needed functionality on basic geometric objects, like points, line segments, and so on. The curved kernel is also parameterized by an AlgebraicKernel that is responsible for all algebraic computations. The declaration is the following:   template < typename BasicKernel, typename AlgebraicKernel >   class Curved_kernel; Arrangement computed with the CGAL Circular kernel and Arrangement packages, on industrial VLSI data. The zooms show the complexity of the data. (Thanks to GeometryFactory for the data and to Pierre Alliez for the picture)
The algebraic kernel consists in fact of several concepts, such as:
- univariate and bivariate polynomials,
- algebraic numbers, ie roots of univariate polynomials,
- roots of systems of bivariate polynomials.
The basic operations necessary to implement geometric predicates and constructions should not impose any specific algebraic tool, so they are kept at a high level, like:

. compare on algebraic numbers and roots of polynomial systems,
. solve on systems of bivariate polynomials,
. critical_points on bivariate polynomials,
. sign_at that computes the sign of a bivariate polynomial evaluated at roots of polynomial systems.

It is crucial to note that the concepts must be general enough to allow also completely different methods, such as interval analysis, that will be used together with exact algebraic methods, for filtering purposes.

Concepts for univariate and bivariate polynomials were reviewed and accepted by the CGAL editorial board.
Models for univariate polynomials, based on the RS software package, should be released soon in CGAL 3.6.
Other models, for both univariate and bivariate polynomials, are expected in the future.

CGAL Packages
2D Circular kernel
3D Spherical kernel
Algebraic Kernel specifications, in collaboration with Eric Berberich and Michael Hemmer

Contributors
Eric Berberich
Pedro M. M. de Castro (internship, summer 2006, now PhD student)
Frédric Cazals
Ioannis Z. Emiris
Julien Hazebrouk and Damien Leroy (project, winter 2006)
Michael Hemmer
Athanasios V. Kakargias (internship, summer 2003)
Menelaos Karavelas
Sylvain Lazard
Sébastien Loriot
Luis Peñaranda
Sylvain Pion
Ilya Suslov (internship, winter 2006)
Elias Tsigaridas
Constantinos Tsirogiannis and Julien Hazebrouk (internships, summer 2005)

Papers