liveBook · Manning

Hyper-spherical region

As explained in Advanced Algorithms and Data Structures

A hyper-spherical region is the set of points within a specified radius of a center point in multidimensional space.

A hyper-spherical region contains every point within a chosen distance of a center point in multidimensional space. In a k-d tree, region search returns all stored points inside that radius. section 9.3.6

A k-d-tree search proceeds by:

  • Checking the distance from the current node to the region center and collecting the point when it lies inside the radius. section 9.3.6
  • Always traversing the branch on the center’s side of the split. section 9.3.6
  • Traversing the opposite branch only when the split line lies within the radius of the center; otherwise pruning it. section 9.3.6

How Advanced Algorithms and Data Structures covers it

How deep it goes
Explains recursive distance testing and split-based pruning, but does not provide complexity analysis.
Examples
Uses a two-dimensional k-d-tree figure and pointsInSphere pseudocode to demonstrate collection and pruning.
What it assumes
Assumes a k-d tree, multidimensional coordinates, split lines, and distance comparisons.
What you can do after
Apply it via recursive k-d-tree region search to collect all points within a chosen radius.
How it connects
Connects hyper-spherical regions to k-d trees, nearest neighbor search, and hyper-rectangular regions.
Cover of Advanced Algorithms and Data Structures
liveBookmanning.com
Read Advanced Algorithms and Data Structures on liveBook Get the book at manning.com

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Advanced Algorithms and Data Structures. The section links point to the parts of the book it draws on.