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

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

ziqichen

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

Tdog

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

motoole2

@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.