CGAL users discussion list

[Olivier Devillers <>]

Le 12/10/15 10:32, Scherrer Daniel a écrit :

Hello

 

When delaunay triangulating in 6D I get much more simplices/full-cells than I would expect. For 3256 vertices there result 2692278 full-cells. I would imagine that the number of full-cells should be about the same as the number of simplices, regardless of the number of dimensions. Although I find it hard to imagine things in 6D ;)

Is there an explanation for the large number of simplices?

 

Full cells are exactly the full dimensional simplices.

In dimension d, the number of simplices is O(n^{\floor( (d+1)/2 )})
where n is the number of vertices.
So it can be very high for some point set.

For 3000 points in 6D you can reach someting in billions.


If you points are evenly distributed, then the complexity is O(n)
but the constant in the O depends on exponentially on d.
(6 in 2D, 26 in 3D, 159 in 4D,...)
Incremental construction of the Delaunay graph in medium dimension [Dwyer, DCG 1991]