CGAL users discussion list

[Bernd Gaertner <>]

 wrote:
> Thanks a lot for your answer!!
> But I have many problems with CGAL::Gmpq type... I use few mathematic
> functions like sqrt() or acos() from "math.h" package...
> Are they defined for CGAL::Gmpq type? and where?

No, they're not defined for CGAL::Gmpq. Please have a look at CGAL's
algebraic concepts 
(http://www.cgal.org/Manual/3.3/doc_html/cgal_manual/Algebraic_foundations/Chapter_main.html)
so see what functionality you can expect from which types. Some types
support sqrt, but acos is not in the concepts at all. If you take the 
result of an exact CGAL computation, round the results to double, apply
some sqrt, acos etc. and feed the results back into the next exact CGAL
algorithm, then chances are intact that the overall error is small,
assuming that you don't use too many algorithms on top of each other.

But please be aware that the intermediate double computations might
for example cause the orientation of a point triple to reverse, and
then the subsequent exact algorithm will get it wrong, simply because
the input is (slightly) wrong. This also means that in the worst case,
there is no precision that can be promised. This is a general problem
with geometric algorithms, as opposed to numerical algorithms (again
I refer to the page http://www.cgal.org/philosophy.html).

It might be worth thinking about ways to eliminate inexact sqrt and
acos computations altogether (internally, many CGAL algorithms do
exactly this). Sometimes, sqrt can easily be avoid by switching to
computations with squared distances, say, and acos might not be
necessary: the next algorithm may need the cosine instead of
the angle anyway. Admittedly, this elimination is usually not
easy, but if you succeed, you will obtain the indicated minimal
unit roundoff in the end.

Best,
Bernd.


> >  wrote:
> > > I work with the CGAL library to compute a bounded voronoi diagram for
> > > my academic research project. I use the Delaunay_triangulation_2 class,
> > > the Voronoi_diagram_2 class, the Min_sphere_of_spheres_d class et other
> > > functions like "intersection".
> > >
> > > I would like to write an article about my subject but I need to know
> > > the computing precision. I use C++ double type and I would like to know
> > > what is the precision that CGAL can ensure? I work with real number (in
> > > double) in the interval [0,1], so how many figures after the comma
> > > without precision's error can I publish?
> > I'm assuming that you speak about the coordinates of the vertices,
> > say, of the computed Voronoi diagram.
> >
> > If your programs exclusively work with type double, and no exact
> > fallback number types (like CGAL::Gmpq or CGAL::MP_Float) are being used,
> > then CGAL cannot give you any strict precision guarantees. The programs
> > may even fail completely for certain inputs.
> >
> > However, if you compute exactly (this is possible by various means
> > in CGAL) and only round the computed results to double in the end, you
> > typically incur only unit roundoff, i.e. the results are correct to around
> > 17 decimal digits. See http://www.cgal.org/philosophy.html
> > for more on the exact computing paradigm in CGAL.
> >
> > Best,
> > Bernd.
> > --
> > You are currently subscribed to cgal-discuss.
> > To unsubscribe or access the archives, go to
> > https://lists-sop.inria.fr/wws/info/cgal-discuss