Re: [Algorithms] Octree leaf neighbours

[Thatcher U. <tu...@tu...>]

From: Thatcher Ulrich <tu...@tu...>
> [re finding a neighbor in an octree]
> It's an O(1) operation on average according to something I read somewhere
> (I think Hanan Samet proved this in one of his books but I don't have a
> reference handy).  The outline of the proof would be something like: half
> of the time, the neighbor is a child of the immediate parent (i.e. one
> generation from a common ancestor); a quarter of the time the neighbor is
> two generations from a common ancestor; an eighth of the time it's three
> generations away, etc.  So over a large number of random queries (N), the
> cost is proportional to N * sum(i=1 --> N: 1/(2^i)).  Divide out the N to
> compute the average cost, and the sum approaches 1 as N approaches
> infinity.

Woah, I made a mess of the math there.  The expected number of pointer
dereferences in a recursive neighbor-finding query should be, on average:

sum(i=1-->infinity : 2*i / (2^i))

which works out to 4, not 1.  Still O(1), fortunately.

--
Thatcher Ulrich
http://tulrich.com