Subject: Thoughts about worldtree
From: Jari P Saukkonen (jsaukkon@cs.Helsinki.FI)
Date: Sun Nov 28 1999 - 23:59:24 EET
I was doing some homework on data structures and had the following idea. I wonder if it would be more efficient to, instead of having a tree with fixed height h (13 atm?), dynamically extend the tree when necessary. We would define a limit on how many objects can the object list in each leaf contain, let it be 50 in this example. When we try to add an object to that list, and it already has 50 other objects, the list node is replaced with branch nod, new leaves (four) are created and the current object list is divided to the new leaves and the procedure will be restarted. Currently, if things get very crowded in one place the overhead for searching specific objects gets high (due to long object lists). By dynamically extending the tree we could enforce a maximum length for the lists making in-list searches more efficient. However, this doesn't affect the usual "get-all-objects-in-radius" query much (after the current system has been optimized to use sibling-links) but if we need to have different kinds of searches in the future it could prove to be more efficient. Just an idea, go ahead and flame. I've had enough trees for this evening! ++ dazzt ps. NO, definitely not for 0.4.0 :) --- | Jari Saukkonen + jari.saukkonen@cs.helsinki.fi : coral -. | programming music graphics | dolphin : | art keyboards web | nah-kolor | +------------------------------------------------+-----------' | Babylon5-inspired 'shadow function' 0 <= t <= 4*pi/3 : x(t) = (sin 8t)^2 * (5 + 3sin 8t) cos (t/2 + (sin 8t)^2) . y(t) = +-(sin 8t)^2 * (5 + 3cos 8t) sin (t/2 + (sin 8t)^2)
This archive was generated by hypermail 2b25 : Tue Feb 12 2002 - 00:00:23 EET