9 SPATIAL TREES

Question 1

What is the primary focus of this chapter?

Answer 1

To improve nearest-neighbor searches using tree-based data structures and spatial partitioning.

The chapter builds on concepts from the previous chapter about finding specific values.

Question 2

What are the two new tree-based data structures introduced?

Answer 2

• Uniform quadtrees
• k-d trees

Question 3

What does the term ‘quadtree’ describe?

Answer 3

A class of two-dimensional data structures that partition each node into four subquadrants.

Based on the original quadtree proposed by Raphael Finkel and Jon Bentley.

Question 4

What is a uniform quadtree?

Answer 4

A structure with equal-sized subregions that mirror the grid structure, proposed by David P. Anderson.

Question 5

What is the main advantage of k-d trees over quadtrees?

Answer 5

K-d trees use a more flexible binary partitioning scheme that can adapt to the data and scale to higher dimensions.

Question 6

What is the main drawback of using grids for two-dimensional data?

Answer 6

They can either consume significant memory with finely grained grids or lead to inefficient searches with coarsely grained grids.

Question 7

How does a uniform quadtree partition space?

Answer 7

Each node is partitioned into four equal-sized quadrants, with a child node for each non-empty quadrant.

Question 8

What are the labels commonly used for the four subtrees in a quadtree?

Answer 8

• NorthWest
• NorthEast
• SouthWest
• SouthEast

Question 9

What information do internal quadtree nodes store?

Answer 9

• Pointers to up to four children
• Metadata such as the number of points in the branch and spatial bounds

Question 10

What is a composite data structure for a QuadTreeNode?

Answer 10

QuadTreeNode {
* Boolean: is_leaf
* Integer: num_points
* Float: x_min
* Float: x_max
* Float: y_min
* Float: y_max
* Matrix of QuadTreeNodes: children
* Array of Points: points
}

Question 11

What is the purpose of storing spatial bounds in a quadtree node?

Answer 11

To simplify the implementation of search algorithms by allowing quick look-up of bounds instead of deriving them.

Question 12

What does the power of quadtrees allow in terms of data structure?

Answer 12

It creates an adaptive, hierarchical grid through branching at each level.

Question 13

What criteria can be used to decide when to stop subdividing a node in a quadtree?

Answer 13

• Enough points to justify a split
• Large enough spatial bounds
• Maximum depth reached

Question 14

What is the typical process for building uniform quadtrees?

Answer 14

Recursively divide allocated space into smaller subregions while checking conditions to stop subdividing.

Question 15

What happens when adding points to a quadtree?

Answer 15

The tree is traversed to find the new point’s location, which may end at a leaf node or an internal dead end.

Question 16

What does the QuadTreeInsert function do?

Answer 16

It ensures the point being inserted is within the quadtree’s bounds and calls QuadTreeNodeInsert.

Question 17

What does the code in QuadTreeNodeInsert function do?

Answer 17

It increments num_points, determines which child bin the point belongs to, and adds the point accordingly.

Question 18

What is the significance of checking splitting conditions when adding a point?

Answer 18

To determine whether to split the current leaf node into subnodes based on the number of points and spatial bounds.

Question 19

What are the components of the Point structure in a quadtree?

Answer 19

• Float: x
• Float: y

Question 20

What is the initial step when checking for a child in a quadtree?

Answer 20

Check whether the child exists; if not, create the child.

Question 21

What values can xbin and ybin take in a quadtree?

Answer 21

Either 0 or 1.

Question 22

What happens at leaf nodes when inserting points into a quadtree?

Answer 22

Points are inserted directly into the node.

Question 23

What condition must be checked before splitting a leaf node in a quadtree?

Answer 23

Whether the splitting conditions are met.

Question 24

How does the code handle splitting a leaf node?

Answer 24

It marks the node as a non-leaf and reinserts the points one at a time.

Question 25

What is the purpose of the FOR loop when reinserting points in a quadtree?

Answer 25

To reinsert points one at a time into the correct children.

Question 26

What must be corrected to avoid double-counting points during reinsertion?

Answer 26

The num_points counter.

Question 27

What is the first step in constructing a uniform quadtree?

Answer 27

Create an empty root node with the necessary spatial bounds.

Question 28

What is the process for removing points from a quadtree?

Answer 28

Delete the point from the leaf node and recursively check for splits.

Question 29

What is the challenge associated with deleting points from a quadtree?

Answer 29

Determining which point to delete, especially with close or duplicate points.

Question 30

What helper function is used to find a point that is close enough for deletion?

Answer 30

approx_equal function.

Question 31

What does the QuadTreeNodeCollapse function do?

Answer 31

Collapses a node with children and returns an array with all the subtree’s points.

Question 32

What does the QuadTreeDelete function check before attempting to delete a point?

Answer 32

It checks that the point lies within the bounds of the tree.

Question 33

What happens if the point to be deleted is found in a leaf node?

Answer 33

It removes the point from the list and decrements the count.

Question 34

What does the recursive deletion function do if it finds a matching point?

Answer 34

Updates the count of points and checks whether the child is empty.

Question 35

What is the purpose of the compatibility test in searching a quadtree?

Answer 35

To check whether the node could contain anything closer than the current candidate.

Question 36

How is the distance from a search target to a node's bounding box computed?

Answer 36

Using the minimum distance formula for x and y coordinates.

Question 37

What is the initial candidate point used in a nearest neighbor search?

Answer 37

A dummy candidate point with infinite distance.

Question 38

Why do we start with a dummy candidate point in a nearest neighbor search?

Answer 38

To ensure any point found will be closer than infinitely far away.

Question 39

What happens as we descend lower in a quadtree during a search?

Answer 39

The spatial bounds tighten.

Question 40

What determines which child node to search first in a quadtree?

Answer 40

The proximity of the child nodes to the query point.

Question 41

What occurs if a node could not contain a better neighbor during a search?

Answer 41

The node and its entire subtree are pruned from the search.

Question 42

What is checked after finding a candidate nearest neighbor in a quadtree?

Answer 42

The compatibility of all remaining child quadrants.

Question 43

What is the result of a successful pruning test in a nearest neighbor search?

Answer 43

The search can skip nodes that cannot contain a better neighbor.

Question 44

What does the process of collapsing a node in a quadtree involve?

Answer 44

Aggregating points from each child and setting the node to be a leaf.

Question 45

What does the pruning test confirm in a nearest-neighbor search?

Answer 45

The pruning test confirms that a quadrant could contain a closer neighbor than the current best point ## Footnote This is illustrated in Figure 9-1.

Question 46

What happens when a child node could contain a closer point during the nearest-neighbor search?

Answer 46

The search proceeds down that pathway to check for closer neighbors.

Question 47

What are the four potential quadrants that vie for attention in a nearest-neighbor search?

Answer 47

NorthWest, NorthEast, SouthWest, SouthEast.

Question 48

Which quadrants can be skipped during the search in a nearest-neighbor algorithm?

Answer 48

The NorthEast and SouthWest quadrants if they are empty, and SouthEast if it's too far away.

Question 49

What is the purpose of the MinDist function in the nearest-neighbor search?

Answer 49

To compute the distance from the target point (x, y) to a node.

Question 50

What does the best_dist parameter represent in the nearest-neighbor search algorithm?

Answer 50

The distance so far.

Question 51

What does a return value of null indicate in the nearest-neighbor search?

Answer 51

There are no points in the current node closer than best_dist.

Question 52

What is the initial distance passed to the nearest-neighbor search wrapper function?

Answer 52

Infinite distance.

Question 53

How are points stored in a KDTreeNode structure?

Answer 53

As an array of Floats.

Question 54

What is the main advantage of a k-d tree over a quadtree?

Answer 54

It allows for flexible partitioning along a single dimension.

Question 55

What does each internal node in a k-d tree store?

Answer 55

The dimension along which it's partitioning (split_dim) and the split value (split_val).

Question 56

What is the structure of a KDTree?

Answer 56

It contains the number of dimensions and a root KDTreeNode.

Question 57

What is a key characteristic of the k-d tree's partitioning method?

Answer 57

It can choose the best split dimension and value based on the data composition.

Question 58

What is the benefit of tracking the bounding box of points in a spatial tree?

Answer 58

It improves the tree's pruning power.

Question 59

What is the problem with using octrees for three-dimensional data?

Answer 59

It doesn't scale gracefully with the number of dimensions.

Question 60

True or False: The k-d tree can split along every dimension at every level.

Answer 60

False.

Question 61

Fill in the blank: A k-d tree combines the spatial partitioning of ______ with the binary branching factor of a binary search tree.

Answer 61

quadtrees.

Question 62

What does the flexible structure of the k-d tree allow for?

Answer 62

More effective searches by tailoring splits based on data composition.

Question 63

In the context of a k-d tree, what does the term 'split_dim' refer to?

Answer 63

The dimension along which the node is partitioned.

Question 64

What is an example of a scenario where k-d trees are more efficient than quadtrees?

Answer 64

Searching for similar conditions in higher-dimensional datasets.

Question 65

What is the primary purpose of choosing the widest dimension in city planning?

Answer 65

To minimize long, narrow zones.

Question 66

What does a median point provide in a spatial tree?

Answer 66

A balanced tree.

Question 67

How can the pruning power of a spatial tree be improved?

Answer 67

By tracking the bounding box of all points within a node.

Question 68

What is the difference in the pruning question when using bounding boxes?

Answer 68

It changes from 'Could a nearest-neighbor candidate exist in the space covered by the node?' to 'Could a nearest-neighbor candidate exist in the bounding boxes of actual points within the node?'

Question 69

What is the benefit of using tighter bounding boxes during node construction?

Answer 69

It allows better adaptation to the data.

Question 70

What do tight bounding boxes allow during search operations?

Answer 70

More aggressive pruning.

Question 71

What is the function of ComputeBoundingBox?

Answer 71

To compute the tight bounding box of the points in a node.

Question 72

What does the RecursiveBuildKDTree function do?

Answer 72

It recursively builds the k-d tree.

Question 73

What are the termination criteria for building a k-d tree?

Answer 73

* Minimum number of points left at the node * Minimum width * Maximum depth

Question 74

What must be checked before building a k-d tree?

Answer 74

That all points have the correct dimensionality.

Question 75

What is a major difference in k-d tree construction compared to quadtree construction?

Answer 75

K-d trees require choosing a single split dimension at each level.

Question 76

What happens if the conditions to split a node are not met in k-d tree construction?

Answer 76

All remaining points are stored in a list at the leaf.

Question 77

What is the advantage of bulk construction of k-d trees?

Answer 77

It allows better adaptation of the tree structure to the data.

Question 78

What operations are performed on a k-d tree?

Answer 78

* Inserting points * Deleting points * Searching

Question 79

How do we determine which branch to take when inserting points into a k-d tree?

Answer 79

Using split_dim and split_val.

Question 80

What is the process for updating the bounding box when inserting a point?

Answer 80

Check each dimension of the new point against the current bounds and update if necessary.

Question 81

What is the key difference in search operations between a quadtree and a k-d tree?

Answer 81

How nodes can be pruned based on the Euclidean distance from a query point.

Question 82

What can cause k-d trees to become unbalanced?

Answer 82

Additions and deletions of points.

Question 83

What do quadtrees allow us to do in terms of data density?

Answer 83

Adapt the resolution of a grid to the density of data points.

Question 84

How does a k-d tree solve the problem of a high branching factor?

Answer 84

By choosing a single dimension along which to split at each node.

Question 85

What tradeoffs are associated with different spatial data structures?

Answer 85

* Program complexity * Computational cost * Memory usage

Question 86

What does the code for building a k-d tree include?

Answer 86

Bookkeeping to fill in essential details at each node.

Question 87

What indicates that a k-d tree node is a leaf?

Answer 87

The is_leaf attribute being True.

Question 88

What does the term 'minimum distance' refer to in k-d trees?

Answer 88

The distance from a query point to the closest possible point in a node's bounding box.