CGAL users discussion list

Le Mer 9 avril 2008 13:40, Jeremy Cope a écrit :
> algorithm therefore makes heavy use of DT3::move_point. I have found
> that while performance is acceptable using a kernel with inexact
> constructions,

Hi,
Note that there are some works in progress to improve the performance of
this move operation in CGAL.

> once I switch to exact constructions to guarantee the
> Voronoi diagram performance degrades badly.

This is expected, to some extent. Maybe you should provide some small
example.

> thrashing as the OS tries to swap pages out to disk. This happens when
> there are only about 30 vertices in the triangulation.

It would also depend on the way these vertices have been defined: if, for
example, each of them has been constructed as circumcenter of the previous
ones, such an explosion of gmp types is to be expected.

> 1. Is DT3::move_point a good way to deal with many moving points?

That's currently the only available one. But this will change.

> In
> the long run, I intend to implement the algorithm of Schaller & Meyer-
> Hermann (2004), but I had thought that the simple remove & re-insert
> strategy would be adequate for small numbers of cells.

It should indeed be perfectly fine for such a small number of cells.

> 2. How important is it to use exact constructions when using the
> DT3::dual functions? Will inexact constructions lead to highly
> inaccurate results,

It is not important, and it may even be a bad idea. Inexact constructions
will be inexact because of the double precision limits. They do not add
other imprecisions than this one.

As a rule of thumb, you can consider that you only need exact
constructions if you intend to plug your results into another geometric
algorithm which expects some specific topological or geometric properties
for its input (such as assuming that points define a simple polygon rather
than a self-intersecting one).

In any case, if you need the exact constructions, you should definitely
not plug such a kernel into DT3. You should instantiate an exact
constructions kernel only for the construction part (there are a few cases
where this would not be suitable, for example if you need to reinsert the
constructed point precisely, but in most situations, you do not really
need that).

-- 
Camille Wormser