Geometric computing
Exact sign of a determinant

Geometric algorithms are known to be highly sensitive to numerical inacurracies.
The exact computation paradigm which is one way to achieve robustness consists in computing exactly the outcome of decision tests. In most geometric algorithms, the decision tests rely on a few number of geometric predicates such as which-side test, orientation test, in-circle test etc. all of which amount to compute the sign of a determinant.

The Prisme project provide different ways to compute exactly the sign of a determinant with integer entries (the first three methods) and even floating point entries.

The reorthogonalization method
This method is based on the Gram-Schmidt reorthogonalization process and has been originally proposed by Clarkson. We have revisited the analysis of Clarkson and proposed a variant of his method.
For more details
Bibliographie
Implementation

The Lattice method
Roughly this method amounts to locate one of the column vector of the determinant with respect to an approximation of the hyperplan span by the others which is more and more refined as needed.
For more details
Bibliographie
Implementation

Modular arithmetic
Modular arithmetic can be used to compute efficiently the sign of a determinant and more generaly of any polynomial expression. This method is in some sense complementary with the two previous ones, because here the sign computation of an expression is as faster as the expression has a small absolute value as opposed to the above cases.
Bibliographie
Implementation

Determinant with floating point entries
The method we propose in such a case is based on a multiple term arithmetic (roughly described as floating point arithmetic with recuperation of the error) and derived from the ideas of J. Shewchuck.
Bibliographie
Implementation

Back to the graphical introduction to Prisme
Back to the welcome page of Prisme