Changeset 27414 in project

Timestamp:

09/12/12 06:28:04 (8 years ago)

Author:

Ivan Raikov

Message:

kd-tree doc: expanded introduction somewhat

File:

• wiki/eggref/4/kd-tree (modified) (1 diff)

wiki/eggref/4/kd-tree

@@ -13 +13 @@
 == Documentation
 
-This library implements a K-D tree, a data structure for organizing
-and searching points in an n-dimensional space.  
-[[http://en.wikipedia.org/wiki/K-d_tree]].
+This library implements a [[http://en.wikipedia.org/wiki/K-d_tree|k-d
+tree]], a data structure for organizing and searching points in
+k-dimensional space. 
+
+The k-d tree is a binary search tree in which every branching node
+contains a k-dimensional point, and every leaf node contains a set of
+points. Every branching node represents a splitting hyperplane that
+divides the space into two parts, known as half-spaces.
+
+Points to the left of the splitting hyperplane are contained in the
+left subtree of the node and points right of the hyperplane are
+contained in the right subtree. The splitting hyperplane is chosen so
+as to be perpendicular to one of the axes in the k-dimensional
+space. The axis at each branching level is chosen in a round-robin
+fashion. For instance, in 3-D space, at level 0, the chosen axis is X,
+so points are divided according to their X-coordinates; at level 1,
+the chosen axis is Y, so the points are divided according to their
+Y-coordinates; at the next branch level the chosen axis is Z, and so
+on.
+
 
 === Point