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.
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.