Java Reference
In-Depth Information
A
C
Figure13.13
Function
InCircle
must check the Euclidean distance between
a record and the query point. It is possible for a record A to have x- and y-
coordinates each within the query distance of the query point C, yet have A itself
lie outside the query circle.
then no record in the left subtree can be within the radius. In such cases, the sub-
tree in question need not be searched, potentially saving much time. In the average
case, the number of nodes that must be visited during a range query is linear on the
number of data records that fall within the query circle.
Example13.7
We will now find all cities in the k-d tree of Figure 13.14
within 25 units of the point (25, 65). The search begins with the root node,
which contains record A. Because (40, 45) is exactly 25 units from the
search point, it will be reported. The search procedure then determines
which branches of the tree to take. The search circle extends to both the
left and the right of A's (vertical) dividing line, so both branches of the
tree must be searched. The left subtree is processed first. Here, record B is
checked and found to fall within the search circle. Because the node storing
B has no children, processing of the left subtree is complete. Processing of
A's right subtree now begins. The coordinates of record C are checked
and found not to fall within the circle. Thus, it should not be reported.
However, it is possible that cities within C's subtrees could fall within the
search circle even if C does not. As C is at level 1, the discriminator at
this level is the y-coordinate. Because 65 25 > 10, no record in C's left
subtree (i.e., records above C) could possibly be in the search circle. Thus,
C's left subtree (if it had one) need not be searched. However, cities in C's
right subtree could fall within the circle. Thus, search proceeds to the node
containing record D. Again, D is outside the search circle. Because 25 +
25 < 69, no record in D's right subtree could be within the search circle.
Thus, only D's left subtree need be searched. This leads to comparing
record E's coordinates against the search circle. Record E falls outside the
search circle, and processing is complete. So we see that we only search
subtrees whose rectangles fall within the search circle.
