Java Reference
In-Depth Information
This section presents two spatial data structures for storing point data in two or
more dimensions. They are the k-d tree and the PR quadtree. The k-d tree is a
natural extension of the BST to multiple dimensions. It is a binary tree whose split-
ting decisions alternate among the key dimensions. Like the BST, the k-d tree uses
object space decomposition. The PR quadtree uses key space decomposition and so
is a form of trie. It is a binary tree only for one-dimensional keys (in which case it
is a trie with a binary alphabet). For d dimensions it has 2
d
branches. Thus, in two
dimensions, the PR quadtree has four branches (hence the name “quadtree”), split-
ting space into four equal-sized quadrants at each branch. Section 13.3.3 briefly
mentions two other variations on these data structures, the bintree and the point
quadtree. These four structures cover all four combinations of object versus key
space decomposition on the one hand, and multi-level binary versus 2
d
-way branch-
ing on the other. Section 13.3.4 briefly discusses spatial data structures for storing
other types of spatial data.
13.3.1
The K-D Tree
The k-d tree is a modification to the BST that allows for efficient processing of
multidimensional keys. The k-d tree differs from the BST in that each level of
the k-d tree makes branching decisions based on a particular search key associated
with that level, called the discriminator. In principle, the k-d tree could be used to
unify key searching across any arbitrary set of keys such as name and zipcode. But
in practice, it is nearly always used to support search on multidimensional coordi-
nates, such as locations in 2D or 3D space. We define the discriminator at level i
to be i mod k for k dimensions. For example, assume that we store data organized
by xy-coordinates. In this case, k is 2 (there are two coordinates), with the x-
coordinate field arbitrarily designated key 0, and the y-coordinate field designated
key 1. At each level, the discriminator alternates between x and y. Thus, a node N
at level 0 (the root) would have in its left subtree only nodes whose x values are less
than N
x
(because x is search key 0, and 0 mod 2 = 0). The right subtree would
contain nodes whose x values are greater than N
x
. A node M at level 1 would
have in its left subtree only nodes whose y values are less than M
y
. There is no re-
striction on the relative values of M
x
and the x values of M's descendants, because
branching decisions made at M are based solely on the y coordinate. Figure 13.11
shows an example of how a collection of two-dimensional points would be stored
in a k-d tree.
In Figure 13.11 the region containing the points is (arbitrarily) restricted to a
128 128 square, and each internal node splits the search space. Each split is
shown by a line, vertical for nodes with x discriminators and horizontal for nodes
with y discriminators. The root node splits the space into two parts; its children
further subdivide the space into smaller parts. The children's split lines do not
cross the root's split line. Thus, each node in the k-d tree helps to decompose the
