Stefan Röttger

← Nearest Neighbor | ● | Nearest Neighbor Search →

Visit the half spaces depth-first:

• first, traverse into the half space
  • that contains the search center
• then, traverse the other half space
  • if it intersects with the search circle that is
    • defined by the currently found closest neighbor
  • otherwise, the other half space cannot contain a closer match

Example:

After traversing into the left half space in the example below, the right half space (the bounding box of the striped area) is farther away than the closest match (the red circle), Therefore, the right half space cannot contribute a closer match and is omitted from tree traversal.

← Nearest Neighbor | ● | Nearest Neighbor Search →