Previous | Next --- Slide 34 of 49
Back to Lecture Thumbnails

Cube root of N grows faster than log(N).


Can someone explain why the intersection cost is O(cube root N)? Thanks.


Does N here represent the number of squares or the side length of the big square?


@Tdog @ziqichen N represents the number of squares in the volume, which we assume to be proportional to the number of primitives. In 2D, the intersection cost would be the square root of N, since a line through this grid intersects approximately this number of grid cells. In 3D, the intersection cost would be the cube root of N.