CGAL users discussion list

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

 

 

18.02.2015, 20:49, "Илья Палачев" <>:

 

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":

 

 

 

Oh. Sorry. I've missed that the graph has label "ratio":

 

The figure shows the ratio of the total number of

tests, as required in Theorem 3 or Corollary 1, to

the corresponding number of local tests, as defined in

Theorem 4, as a function of the total number of sam-

ple directions chosen.

 

It means that there was something like Theta(n^2) or Theta(n^2 log n) in that case.

You're right.

 

But is there any algorithm of complexity = Theta(n^2) of Theta(n^2 log n) for this case?

It is much better than Theta(n^4) for testing of all quadruples.

 

What do you think?