13.3.1. Spatial Data Structures¶

• BST can take any comparable type, but is a one-dimensional key.

  • XY coords are 2-dimensional. Could combine? Would help for exact match, but not ranges (find in a search circle).

  • Could use two BSTs? Of narrow search on X? (would find everything in a vertical band, each would have to be checked for distance)

• These same issues apply for any other search structure that takes a one-dimensional key.

13.3.2. KD Trees¶

KD Trees are identical to BSTs, except they store multi-dimensional data and rotate through the keys at each level.

• Each level has a “discriminator” value.

• The levels rotate through the dimensions of the multi-dimensional key.

13.3.3. K-D Tree Visualization¶

13.3.4. Bintree 1¶

The Bintree is similar to the KD-tree in that each level has splits and direction-finding driven by one dimension in the key, and it alternates through the dimensions.

• But, the split is in the middle of the key range (image space vs. object space splitting)

• The Bintree is a trie: No data at the internal nodes, and some leaf nodes can be empty.

13.3.5. Bintree 2¶

13.3.6. Bintree 2¶

13.3.7. PR Quadtrees¶

Like the Bintree, but splits in all dimensions at once. For two dimensions, this means 4 children (three dimensions would mean 8 children).

Some similarity to DNA trees.

13.3.8. Point Quadtree¶

• Like PR Quadtree, but using Object Space Decomposition.

• Not a trie

• Fills out our last data structure in the design space.

13.3.9. Extending the Concept¶

Spatial data structures have a Decomposition Rule.

• The rule might be to allow more than one point in a node.

13.3.10. Going Beyond Points¶

• We can store any objects, not just points.

• A sensible decomposition rule can make this efficient.

• For example, we could store boxes in 2D.

  • But what about boxes that overlap? Splitting can’t separate them.

  • So, the system has to allow for an arbirary number of overlapping boxes.

  • Since we need to allow for storing a list of boxes anyway, we might as well allow more than one even when there is no split.

  • Example rule: A node can store a list of up to three boxes, or as many boxes as required if they all share a common intersection.

  • If the boxes in the node violate this rule, then split it (during insertion).

  • If an internal node has two leaf children that, together, pass the rule, then merge them (on deletion).

• This approach supports efficient detection of box intersections.