A nearby point, a point inside a rectangle, and a line crossing a region require spatial evidence. This topic compares structures by what their boundaries mean and how those boundaries justify skipping work.
What you should be able to explain¶
By the end of this topic, you should be able to connect each index’s stored information to its splitting/grouping rule, trace exact and range queries at boundaries, justify safe pruning, and distinguish candidate filtering from exact geometry checks. You should also be able to qualify a cost claim using height, visited records/cells and output size.
How to use the readings¶
Read the question, prose and diagrams first. Before opening a Show explanation panel, predict the branch, answer set or stopping decision and say why. If your prediction differs, revisit the named rule rather than memorising the trace. All essential explanations remain in the main reading; the panels contain feedback on the checks.
Each reading begins with two learning goals and a prerequisite link. Near its end, a short misconception reminder and two ungraded checks help you decide whether to move on. These are original self-study examples, independent of course assessments.
Reading route¶
Spatial queries and a reference scan: fix objects, distance units and query boundaries.
K-d trees: construction, exact search, range search, shape and limitations, nearest neighbours, and deletion with a cost summary.
Point quadtrees: insertion, exact and range search, then nearest search, deletion and costs.
Point-region quadtrees: replace pivot locations with fixed cell midpoints, then read insertion
/exact /range and nearest /deletion /merging. R-trees: read enclosing rectangles and the given tree, then range candidates and exact refinement. Those helpers support construction concepts, exact lookup, nearest and deletion.
Compare the spatial indexes: reuse the same point/query example and account for different kinds of work.
Read BST terminology and recursion first. The point and PR operations use iterative traversal. The AVL rotation comparison remains useful, but AVL code is not a prerequisite.
The k-d-tree core follows the additional lecture’s seven-point example. The quadtree and R-tree readings are original extensions, with primary references linked on their pages. They do not change CS2040HS assessment scope. Point examples use finite numeric coordinate pairs and ignore repeated identical points; R-tree examples preserve distinct line identifiers.
The sidebar groups readings by four methods. Compare the same five operations for each: construction/insertion, exact lookup, range search, nearest neighbour and deletion, with time and space costs. Some helpers are introduced before the operation that reuses them; the R-tree exact lookup, for example, uses the preceding range-candidate traversal.
The standalone Python example includes all listed point-tree operations and given-tree R-tree exact/range/nearest queries. General dynamic R-tree insertion, splitting and condensation are explained with worked traces, not implemented. Static k-d median construction and R-tree packing also remain conceptual.
Keep the code context clear¶
| Reading route | Definitions to have available |
|---|---|
| K-d insertion, exact, range and nearest | Start with KDNode and the shared root from construction, then read the query function on its own page |
| Point and PR quadtrees | Start with the spatial-query helpers, then the point-quadtree definitions, then PR operations |
| R-tree query and refinement | Use the spatial-query helpers and the given R-tree/segment definitions before the query code |
The downloadable comparison script supplies its own definitions and data. It includes the k-d exact, nearest and deletion listings as well as the point/PR updates and R-tree queries. Helpers and their prerequisites are linked on each operation page.
Where to check your understanding¶
| If you are unsure about… | Revisit these checks |
|---|---|
| Query boundaries and pruning evidence | Spatial-query contracts |
| Active axes and coordinate ties | K-d insertion and exact search |
| Which branches can contain answers | K-d ranges and nearest search |
| Height, balance and construction assumptions | K-d shape |
| Point pivots versus fixed midpoint cells | Point quadtrees and PR concepts |
| Buckets, redistribution and stopping | PR operations |
| Enclosures, candidates and exact matches | R-tree representation and queries |
| Comparing costs and choosing a structure | Spatial-index choices |
Complete the operation checks¶
Code listings offer Python, JavaScript and Julia tabs where a runnable example is present. Python remains the explanation and trace language; see the language guide for native conventions and runnable topic downloads.