CGAL users discussion list

[Olivier Devillers <>]

Le 18/02/15 17:38, Илья Палачев a écrit :

Okay :)

 

Let's say that we have real-world example: we know that all points lie on the plane in some regular order...Not uniform distribution, but... something like that... say: points are uniformly distributed on the sphere and then pertrurbed from their initial position.

Stupid exhaustive search shows that there are only O(n) local positive quadruples. How can we find them?

 

Can you suggest anything more fast that the exhaustive search?

 

Are you sure ?

If you search for empty triangles for uniform distribution you have clearly Omega(n^2)
(any segment can be completed in an empty triangle.
I would guess something like n^2 log n for the correct result.

I also would expect something similar for triangles containing one point.