An overlap check detects problematic overlap between sibling bounding envelopes in an SS+-tree. It supports maintenance after splits, merges, deletions, or moving points and children across siblings. section 10.5.4
Exact intersection volume for two hyperspheres is unsuitable for a heuristic because the generic calculation requires an expensive integral. A cheaper containment test compares centroids and radii: identify the larger sphere with radius R and the smaller with radius r, then test whether the smaller center lies inside the larger sphere and its centroid distance is less than R-r. section 10.5.4 section 10.5.4
A ratio threshold can soften the binary test by comparing centroid distance with R-r; as the ratio approaches one, it approximates increasing overlap. When the condition is satisfied, reorganize the node by clustering all grandchildren with k-means and replacing the node’s children with the resulting clusters. section 10.5.4 section 10.5.4
Figure 10.28 An example where the grandchildren-split heuristic could be triggered and would lower the nodes overlap. The SS-tree in the example has m==2 and M>=5. The k-means split heuristic is run on the points A-L, with k==5. Notice how k-means can (and sometimes will) output fewer clusters than the initial number of centroids. In this case, only four clusters were returned.
The figure traces a node-overlap case where clustering points A–L through a grandchildren split can reduce overlap; k-means may return fewer clusters than requested. section 10.5.4
