CGAL users discussion list

[Илья Палачев <>]

18.02.2015, 20:17, "Olivier Devillers" <>:

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.

 

 

In this article http://ssg.mit.edu/~willsky/publ_pdfs/133_pub_MIV.pdf

authors published the following graph:

 

It shows that in their case there was 3000 local tests for 600 directions.

Maybe I'm misunderstanding their definition of "local positive cone tests":

 

DEFINITION 1 (LOCAL FAMILY) Given a set S of m distinct unit vectors in R^n and a member from this set u_k, we define the local family corresponding to u_k to be the set of all distinct (n + 1)-tuples of vectors from S such that u_k is one element of the (n + 1)-tuple and the remaining n vectors of the ( n + 1)-tuple contain only themselves and uk from S in their full positive cone.

 

What do you think about that?