News for hackers. Stuff that matters.

A comment on Using k-d trees to efficiently calculate nearest neighbors in 3D vector space. Parent comment

Re:Using k-d trees to efficiently calculate nearest neighbor... by boulos on Saturday February 10, 2018 @03:32PM (#16349419)
You’ve just described a single axis kd-tree roughly. Which means you’ll also perform catastrophically for patterns with say a line in the Z-axis. It’s not that hard to do a proper spatial tree. If you hate kd-trees, an octree or a grid are also more robust than a “single axis binary split tree”.
[ Parent | on HN ]
Re:Using k-d trees to efficiently calculate nearest neighbor... by geophile on Saturday February 10, 2018 @06:01PM (#16350135)
Not sure what you mean by a single-axis kd-tree.

Z-order + sorted array/tree/etc. is a generalization of an oct-tree. An octtree is just z-order combined with a degree 8 trie. And an octtree is simply an encoding of a 3-d grid.

So I really don't understand your objections.

Also, I haven't tried NN search using z-order, but range searches work very well. The partitioning induced by z-order adapts well to all sorts of distributions.

[ Parent | on HN ]
Re:Using k-d trees to efficiently calculate nearest neighbor... by geophile on Saturday February 10, 2018 @07:31PM (#16350449)
Oh! I see the problem.

I don't mean just a tree keyed on the z-axis. I mean z-order: https://en.wikipedia.org/wiki/Z-order

[ Parent | on HN ]
Re:Using k-d trees to efficiently calculate nearest neighbor... by boulos on Saturday February 10, 2018 @08:21PM (#16350623)
Ahh! I wasn’t sure, so sadly I chose “z as in z axis” not Z as in Z/space-filling/Hilbert/Morton order. That’s a grid in disguise! :).
[ Parent | on HN ]