0
\$\begingroup\$

I've understood that KD tree split points using the median while cycling on each axis. I've also understood that at each node traversal, a nearest search must use a sphere to store to nearest neighbor (in case the query point is very close to the split median).

What I don't understand, is why median are always aligned with one point? Does that mean nodes are always storing one point? Does that mean each node can only have one point and 2 childs nodes ?

\$\endgroup\$
0
\$\begingroup\$

Because that's how binary trees work, of which kd-trees are a special case.

In a binary tree, each node has

  • exactly one value
  • 0-1 child-nodes carrying a smaller value
  • 0-1 child-nodes carrying a larger value

What sets kd-trees apart from normal binary trees is the way they decide what's "larger" and what's "smaller": The property which decides this cycles between tree levels.

The median of a node in a kd-tree is actually a coordinate of its value. You don't need an extra variable for this.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.