Re: [Algorithms] Octree leaf neighbours

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

On Sat, 15 Jul 2000, Sam Kuhn wrote:

> I'm creating an octree, and need to maintain pointers between neighbouring
> *leaves*, and do it quick. The only way I can think of is to skip back up
> the tree and down the neighbouring branches to locate each of the 6
> neighbours. This doesn't seem very fast.

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.

So while the traversal may *seem* slow when looking at the code, it
probably isn't as slow as you think.

--
Thatcher Ulrich
http://tulrich.com