CGAL users discussion list

[Adam Getchell <>]

On Oct 12, 2015, at 1:53 AM, Olivier Devillers <> wrote:

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,...)
[Dwyer, DCG 1991]

Awesome, thanks for the reference Olivier!

I had been using a naive factor like 4*simplices = points, whereas I noted that in practice more cells were being generated than vertices.

A more exact formula, e.g. ES_n=6.77n for d=3 and ES_n=31.78n for d=4, is extremely helpful!

Merci!

Adam Getchell
about.me/adamgetchell