A metric measures separation between pairs of points. It is nonnegative, equals zero only for identical points, is symmetric, and satisfies the triangle inequality. section 10.3.1
In an SS-tree, the distance function is a structural parameter: implementations may use Euclidean distance in k-dimensional space or another valid metric. section 10.3.1
Testing a sphere boundary
To decide whether a target belongs within a node’s bounding sphere, compute the metric distance from the target to the sphere’s centroid and test whether it is at most the radius. section 10.3.1
Figure 10.10 Search on a SS-tree: the first few steps of searching for point Z. The SS-tree shown is derived from the one in figure 10.9, with a few minor changes; the name of the entries have been removed here and letters from A to W are used to reduce clutter. (Top) The first step of the search is comparing Z to the spheres in the tree’s root: for each of them, computes the distance between Z and its centroid, and checks if it’s smaller than the sphere’s radius. (Bottom) Since both S1 and S2 intersect Z, we need to traverse both branches and check spheres S3 to S6 for intersection with Z.
Trace how an SS-tree compares a target with centroid-radius spheres and traverses every branch whose sphere intersects it. section 10.3.1
