The concept Kinetic::FunctionKernel encapsulates all the methods for representing and handing functions. The set is kept deliberately small to easy use of new Kinetic::FunctionKernels, but together these operations are sufficient to allow the correct processing of events, handling of degeneracies, usage of static data structures, run-time error checking as well as run-time verification of the correctness of kinetic data structures. The computation of a polynomial with the variable negated is used for reversing time in kinetic data structures and can be omitted if that capability is not needed.


The type of function being handled.

The basic representational number type.

A type representing the roots of a Function.

A model of RootStack. These objects can be created by calling the root_stack_object method with a Function and two (optional) Root objects. The enumerator then enumerates all roots of the function in the open inverval defined by the two root arguments. They optional arguments default to positive and negative infinity.

The traits for the Root_enumerator class.

Each of the following types has a corresponding type_object method (not explicitly documented) which takes a Function as an argument.

A functor which returns the sign of a Function at a NT or Root.

A functor which returns sign of a function immediately after a root.

The following type is used to construct functions from a list of coefficients. To get an instance use the construct_function_object() method.

This functor can be used create instances of Function. See its reference page FunctionKernel::ConstructFunction for more details.

The following functor likewise have a type_object method, but these take arguments other than a Function. The arguments are given below.

This functor, creation of which requires two Roots, returns the sign of a passed function between the pair of roots.

This functor computes the derivitive of a Function. Construction takes no arguments.

The following methods do not require any arguments to get the functor and take one Function as a functor argument.

Map f(x) to f(-x).

Has Models

POLYNOMIAL::Kernel<RootStack>, POLYNOMIAL::Filtered_kernel<RootStack>.

See Also



We provide several models of the concept, which are not documented separately. The models of Kinetic::SimulationTraits all choose appropriate models. However, if more control is desired, we here provide examples of how to create the various supported Kinetic::FunctionKernel.

A Sturm sequence based kernel which supports exact comparisons of roots of polynomials (certificate failure times):

typedef CGAL::POLYNOMIAL::Polynomial<CGAL::Gmpq> Function;
typedef CGAL::POLYNOMIAL::Sturm_root_stack_traits<Function> Root_stack_traits;
typedef CGAL::POLYNOMIAL::Sturm_root_stack<Root_stack_traits> Root_stack;
typedef CGAL::POLYNOMIAL::Kernel<Function, Root_stack> Function_kernel;

A wrapper for CORE::Expr which implements the necessary operations:

typedef CGAL::POLYNOMIAL::CORE_kernel Function_kernel;

A function kernel which computes approximations to the roots of the polynomials:

typedef CGAL::POLYNOMIAL::Polynomial<double> Function;
typedef CGAL::POLYNOMIAL::Root_stack_default_traits<Function> Root_stack_traits;
typedef CGAL::POLYNOMIAL::Numeric_root_stack<Root_stack_traits> Root_stack;
typedef CGAL::POLYNOMIAL::Kernel<Function, Root_stack> Function_kernel;

When using the function kernel in kinetic data structures, especially one that is in exact, it is useful to wrap the root stack. The wrapper checks the sign of the certificate function being solved and uses that to handle degeneracies. This is done by, for the inexact solvers

typedef Kinetic::Derivitive_filter_function_kernel<Function_kernel> KDS_function_kernel;
and for exact solvers
typedef Kinetic::Handle_degeneracy_function_kernel<Function_kernel> KDS_function_kernel;

For exact computations, the primary representation for roots is the now standard choice of a polynomial with an associated isolating interval (and interval containing exactly one distinct root of a polynomial) along with whether the root has odd or even multiplicity and, if needed, the Sturm sequence of the polynomial. Two intervals can be compared by first seeing if the isolating intervals are disjoint. If they are, then we know the ordering of the respective roots. If not we can subdivide each of the intervals (using the endpoints of the other interval) and repeat. In order to avoid subdividing endlessly when comparing equal roots, once we subdivide a constant number of times, we use the Sturm sequence of p and p'q (where p and q are the two polynomials and p' is the derivative of p) to evaluate the sign of the second at the root of the first one directly (note that this Sturm sequence is applied to a common isolating interval of the roots of interest of both polynomials).