CGAL users discussion list

[Damian Sheehy <>]

Sylvain,

 

Thank you for enlightening me!  :)

 

Manuel,

 

Your non-hierarchical triangulation (dt_build in your notation) calls the dt.insert(begin, end) interface. This interface performs preprocessing to sort the points along a Hilbert curve which improves the performance of insertion. I did not factor this in when I compared computation times for the Delaunay and the Delaunay+hierarchy construction. To perform an apple-to-apple comparison of the performance of these two algorithms you should use the dt/dh.insert(Point) interface.

 

So in summary, the hierarchy is not being leveraged during construction because the sort ensures the resulting sequence of points is in close geometric proximity; the hierarchy is not being leveraged during nearest_vertex queries because you are already providing a good starting hint. Conclusion, the hierarchy is not doing anything for you so you don't need it.

 

 

Best regards,

 

Damian

 

On Sun, Apr 19, 2009 at 8:10 AM, Sylvain Pion <> wrote:

Hi Damian,

Damian Sheehy a écrit :

For a random set of points the Delaunay hierarchy should build a triangulation in much less time than the conventional Delaunay without a hierarchy. The numbers do not reflect that, so something is wrong. I will run your example tomorrow and see what I get. . .

This is not true anymore in recent CGAL releases, more precisely
since the introduction of a spatial sorting preprocessing phase (BRIO).

--
Sylvain Pion
INRIA Sophia-Antipolis
Geometrica Project-Team
CGAL, http://cgal.org/
--

You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss