Project

I have finished implementing the kd-tree. My issue was not actually with the traversal code but instead I was running some methods from an object before the object was allocated. Quite an oversight. Now thats out of the way, I have been able to test my kd-tree.

Here we have three different algorithms plotted. The naive algorithm performs horrendously. Next we have a kd-tree that is built without a heuristic. The plane position is always chosen by taking the midpoint according to some axis. Lastly, a kd-tree with the surface area heuristic is plotted. Both the kd-trees are logarithmic in time, which is great to see. As expected the running time is better for SAH.

In exchange for the better performance with SAH, we suffer horrendous time complexity for build time. It is exponential in time.

This results are encouraging and gives me plenty to discuss.