CGAL users discussion list

[Jeremy Cope <>]

I am trying to use Delaunay_Triangulation_3 to calculate the Delaunay  
triangulation and Voronoi diagram of a set of moving points in 3D. My  
algorithm therefore makes heavy use of DT3::move_point. I have found  
that while performance is acceptable using a kernel with inexact  
constructions, once I switch to exact constructions to guarantee the  
Voronoi diagram performance degrades badly.

More specifically, DT3::remove (which is called by move_point) seems  
to allocate vast quantities of memory evaluating expressions involving  
GMP objects. This quickly fills up my physical memory, leading to  
thrashing as the OS tries to swap pages out to disk. This happens when  
there are only about 30 vertices in the triangulation.

I have two questions:

1. Is DT3::move_point a good way to deal with many moving points? 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.

2. How important is it to use exact constructions when using the  
DT3::dual functions? Will inexact constructions lead to highly  
inaccurate results, or are they acceptable when double precision  
floating point results are sufficient?

Thanks,
Jeremy

Reference:
Schaller, G. and Meyer-Hermann, M. (2004).  Kinetic and dynamic  
Delaunay tetrahedralizations in three dimensions, Computer Physics  
Communications, 162(1), 9-23. doi:10.1016/j.cpc.2004.06.066

PS. Some context: I am using CGAL::Delaunay_Triangulation_3 in an  
agent-based model of skin cells as part of my PhD project.
--
The forceps of our minds are clumsy forceps, and crush the truth a  
little in taking hold of it. - H. G. Wells

Jeremy Cope
Ph.D. Student, Computational Systems Biology
Department of Computer Science, University of Sheffield