CGAL users discussion list

[Olivier Devillers <>]

On 15 Sep 2016, at 18:29, Илья Палачев <> wrote:

Hi Olivier,

 

Thanks for quick answer. My comments below.

 

15.09.2016, 18:31, "Olivier Devillers" <>:

 

On 15 Sep 2016, at 14:42, Илья Палачев <> wrote:

 

Hi,

 

That's an interesting thread.

 

In this article it's said that

 

The hierachical tessellation makes the asymptopic point location time to be O(() log(n)), which is optimal

 

Does it mean that using CGAL's Delaunay_triangulation_3 I can construct 3D dynamic hull for N points, and then locate each new point in time O(log N) ?

 

 

 

Are there any asymptotic estimates for the construction of 3d Delaunay triangulation? Is it O(N log N) ?

 

of course not, if the result as quadratic size, you cannot compute it in sub quadratic time.

 

Yes, it's clear. According to Theorem 8 from your article, the guaranteed working time of algorithm is O(N^2) for 3D case.

 

The exact hypotheses on your point set are:

-  For any random subset of your point set, the size of the 3D Delaunay triangulation is linear in the number of points

- You construct the Delaunay triangulation inserting the points in a random order  (this is for construction, not for point location)

 

if the first hypothesis is not fulfilled you can express the complexity in terms using the function: r—> expected size of the triangulation of a subset of size r

https://hal.inria.fr/inria-0016671

 

Thanks for this link.

 

For my use case it seems that all points lie almost (with some "epsilon" precision) on the surface of some polyhedra, and points are the "samples" of its surface. It seems to me that for this case the conditions of Theorem 12 from [ https://graphics.stanford.edu/courses/cs468-02-winter/Papers/linearDT.pdf ] hold and, hence, the first hypothesis holds, too. Is it true, how do you think?

 

Not  exactly. 

The result of Attali&Boissonnat is for an (epsilon,kappa) sample. So the points are (exactly) on the polyhedron

and satisfy some deterministic condition: (not too many points close together, no big void in the sampling).

It seems that your points are not on the surface and your sampling conditions are not detailed.

It should work well, but you cannot deduce directly a formal proof of good complexity.

Olivier