Re: [Algorithms] Octree leaf neighbours

[Martin G. <bz...@wi...>]

And in addition you can save much time if you hold the tree in an array. This
saves the parent links, too :)

-----Original Message-----
From: Thatcher Ulrich <tu...@tu...>
To: gda...@li...
<gda...@li...>
Date: 16 Þëè 2000 ã. 16:49
Subject: Re: [Algorithms] Octree leaf neighbours


>
>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
>
>
>
>_______________________________________________
>GDAlgorithms-list mailing list
>GDA...@li...
>http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
>