\( \newcommand{\E}{\mathrm{E}} \) \( \newcommand{\A}{\mathrm{A}} \) \( \newcommand{\R}{\mathrm{R}} \) \( \newcommand{\N}{\mathrm{N}} \) \( \newcommand{\Q}{\mathrm{Q}} \) \( \newcommand{\Z}{\mathrm{Z}} \) \( \def\ccSum #1#2#3{ \sum_{#1}^{#2}{#3} } \def\ccProd #1#2#3{ \sum_{#1}^{#2}{#3} }\)
CGAL 4.5.1 - Kinetic Framework
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Groups Pages
List of all members | Classes
Kinetic::FunctionKernel Concept Reference
Main Concepts

Definition

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.

Has Models:

POLYNOMIAL::Kernel<RootStack>

POLYNOMIAL::Filtered_kernel<RootStack>

See Also
Kinetic::RootEnumerator

Example

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).

Concepts

conceptConstructFunction
 The concept ConstructFunction is used to construct functions. More...
 
conceptFunction
 The concept Function represents a function. More...
 

Types

typedef unspecified_type NT
 The basic representational number type.
 
typedef unspecified_type Root
 A type representing the roots of a Function.
 
typedef unspecified_type Root_stack
 A model of RootStack. More...
 
typedef unspecified_type Root_enumerator_traits
 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.

typedef unspecified_type Sign_at
 A functor which returns the sign of a Function at a NT or Root.
 
typedef unspecified_type Sign_after
 A functor which returns sign of a function immediately after a root.
 

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

The arguments are given below.

typedef unspecified_type Sign_between_roots
 This functor, creation of which requires two Roots, returns the sign of a passed function between the pair of roots.
 
typedef unspecified_type Differentiate
 This functor computes the derivitive of a Function. More...
 

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

typedef unspecified_type Negate_variable
 Map \( f(x)\) to \( f(-x)\).
 

Member Typedef Documentation

typedef unspecified_type Kinetic::FunctionKernel::Differentiate

This functor computes the derivitive of a Function.

Construction takes no arguments.

typedef unspecified_type Kinetic::FunctionKernel::Root_stack

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.