CGAL users discussion list

[Marc Glisse <>]

On Sun, 7 Jun 2015, Hadidi, Lars wrote:

> I'd like to know which technique is employed to guarantee the 
> correctness on the floating point calculations.

It depends on which kernel and which predicate you are considering. One 
typical example would be, to compute the sign of a polynomial like 
orientation:
1) do the computation with double, rounding to nearest, then if we are far 
enough from 0 (using a precomputed threshold specific to each predicate) 
we can stop here.
2) do the computation with interval arithmetics (of double). If the 
resulting interval does not contain 0, we can stop here.
3) do the computation with an exact, arbitrary-precision number type 
(based on GMP unless you specifically ask for something else).

> Do you use the method proposed by J.R. Shewchuck for adaptive precision 
> floating point arithmetic ?

Not currently, though we might add some support for that at some point, 
there have been several experiments.

> If not, how fast is your method compared to it ??

It depends on the predicate, and on implementation details. Bruno Lévy's 
geogram should be better tuned to recent hardware than Shewchuk's code. On 
a very simple predicate like orientation in 2d, if the number of 
degenerate configurations is high (that is unlikely), Shewchuk's approach 
is a bit faster than CGAL. As the predicate becomes more complicated (say 
in_sphere in dimension 5), if the number of degenerate configurations is 
high, CGAL is faster.

--
Marc Glisse