Spatial and Multidimensional Data Structures

Introduction and Context

Many data structures are designed for one-dimensional keys: integers, strings, timestamps, or ordered records. Spatial data is different. A point is described by several coordinates, and useful queries depend on geometric relationships such as proximity, containment, intersection, and overlap. In a geographic information system (GIS), a query may ask for all hospitals within 5 km of a location. In robotics, a planner may need to identify obstacles intersecting a proposed path. In computer vision, a system may search for nearby feature descriptors or image regions. In scientific computing, simulations may repeatedly locate particles, cells, or mesh elements in space.

A spatial data structure organizes multidimensional objects so that geometric queries avoid examining every object. The central challenge is the curse of dimensionality: as the number of dimensions increases, the volume of the search region and the cost of partitioning it grow rapidly, while the distinction between near and far points becomes less useful.

This chapter examines k-d trees, quadtrees, octrees, R-trees, and spatial hashing. It compares their geometric assumptions, update behavior, memory requirements, and query performance, and relates their use to GIS, robotics, computer vision, and scientific computing.

Learning Objectives

By the end of this chapter, the reader should be able to:

1. Explain why multidimensional searching differs from one-dimensional searching.
2. Construct and query k-d trees, quadtrees, octrees, R-trees, and spatial hash tables.
3. Analyze range, nearest-neighbor, intersection, and collision queries.
4. Select an appropriate structure for static, dynamic, uniform, clustered, or high-dimensional data.
5. Evaluate the effect of dimensionality, skew, object size, and update frequency.
6. Apply spatial indexing methods to GIS, robotics, computer vision, and scientific workloads.
7. Recognize numerical, ethical, and operational risks in spatial data systems.

1. Spatial Query Foundations

Let a point in k-dimensional space be represented as

p = (x₁, x₂, ..., x_k).

For Euclidean distance, the distance between points p and q is

where p_i and q_i are coordinates in dimension i. This formula assumes a Euclidean coordinate system and comparable coordinate units. It should not be applied directly to latitude and longitude over large areas because geographic coordinates lie on a curved surface. GIS applications commonly use a projected coordinate reference system or a geodesic distance calculation.

Important spatial queries include:

• Point query: locate an object at a specified coordinate.
• Orthogonal range query: report points or objects within an axis-aligned rectangle, box, or hyperrectangle.
• Nearest-neighbor query: find the object minimizing distance to a query point.
• k-nearest-neighbor query: return the k closest objects.
• Intersection query: report objects whose regions intersect a query region.
• Containment query: identify objects entirely inside or containing a specified region.
• Window query: another name for an orthogonal range query.
• Collision query: determine whether geometric bodies overlap or whether a moving body intersects obstacles.

For an axis-aligned rectangle in two dimensions, the query region can be written as

R = [x_min,x_max] × [y_min,y_max].

A point (x,y) is inside R when x_min ≤ x ≤ x_max and y_min ≤ y ≤ y_max. Boundary conventions must be specified: closed intervals include boundaries, whereas half-open intervals avoid duplicate ownership when adjacent regions share an edge.

1.1 Spatial locality and pruning

All structures in this chapter exploit locality. If a node represents a region that cannot contain a query result, the entire node can be skipped. A bounding region is therefore more important than the exact shape of every object during the first search stage.

For a node with bounding box B and a query point q, a lower bound on the distance to any point in B is the distance from q to the closest point of B. In two dimensions, if B has coordinate intervals [a_i,b_i] and q has coordinate q_i, the coordinate-wise distance is

and the Euclidean lower bound is

This bound is exact for an axis-aligned box under Euclidean distance. A nearest-neighbor algorithm can prune B whenever its lower bound is no smaller than the best distance already found.

2. k-d Trees

A k-d tree is a binary space-partitioning tree for points in k dimensions. Each internal node selects one coordinate axis and divides the data with a hyperplane perpendicular to that axis. The simplest policy cycles through dimensions: at depth d, split on dimension d mod k. More sophisticated implementations choose the dimension with greatest spread or use balanced median splits.

For a two-dimensional point set, a root may split on x, its children on y, and the next level on x again. Each node stores a point and represents a region of space. A median split produces approximately equal populations in the two subtrees, although the geometric regions may have very different shapes.

2.1 Construction

A balanced construction proceeds as follows:

1. Choose a splitting dimension.
2. Select the median point according to that coordinate.
3. Store the median at the node.
4. Recursively construct the left subtree from points below the median.
5. Recursively construct the right subtree from points above the median.

With an efficient selection or sorting strategy, construction is commonly O(n log n) for n points, although exact cost depends on implementation. A naïve insertion order can produce a highly unbalanced tree with height approaching n.

A balanced tree has height approximately O(log n). This does not mean every spatial query takes logarithmic time: backtracking may visit many branches when the query boundary intersects several regions.

2.2 Range searching

For an orthogonal range query, the algorithm compares the query interval with the node's splitting coordinate. A subtree can be skipped if its entire region lies outside the query. If the splitting plane intersects the query region, both subtrees may need examination.

The practical cost is often described as output-sensitive: it depends on the number of reported points as well as the pruning achieved. In low dimensions and for well-distributed data, k-d trees are effective. In high dimensions, many branches may intersect the query region, reducing the benefit of indexing.

2.3 Nearest-neighbor search

Nearest-neighbor search first descends toward the side containing the query point. It maintains the best distance found and then backtracks. The opposite subtree is searched only if its region could contain a closer point.

The correctness condition is important. A branch cannot be pruned merely because its splitting coordinate is on the opposite side of the query. It may still contain a point closer in other coordinates. Pruning is valid only when a lower-bound distance exceeds the current best distance.

2.4 Strengths and limitations

Deletion is more complicated than insertion because replacing a deleted point must preserve splitting invariants. Dynamic systems may use lazy deletion, periodic rebuilding, or balanced variants.

3. Quadtrees and Octrees

A quadtree recursively divides a two-dimensional region into four equal quadrants. An octree performs the analogous operation in three dimensions, dividing a cube or rectangular volume into eight children. More generally, a regular grid subdivision in k dimensions has up to 2^k children per node.

Unlike a k-d tree, which normally makes one binary split at a time, a quadtree or octree partitions all coordinate axes simultaneously at each level. The structure is naturally hierarchical and is particularly useful for raster data, occupancy maps, image regions, terrain, volumetric data, and collision environments.

3.1 Region and point quadtrees

A region quadtree represents a spatial field or image. A node is homogeneous if all its cells have the same value; otherwise it is subdivided. A point quadtree stores points and subdivides when a region exceeds a capacity threshold.

A capacity-based quadtree is usually preferable for point data because it avoids subdividing empty space indefinitely. A node may store up to c objects, where c is a design parameter. Subdivision continues until the capacity is respected or a minimum cell size is reached.

3.2 Octrees in three dimensions

Octrees are common in robotics and scientific visualization. An occupancy octree labels volume cells as free, occupied, or unknown. Large homogeneous regions can be represented by one node, while detailed subdivision is reserved for boundaries and obstacles.

An octree can support ray traversal, collision testing, surface extraction, and adaptive simulation. Its memory cost can nevertheless become high near complex surfaces, where many nodes are needed to represent fine detail.

3.3 Advantages and limitations

Regular subdivision provides predictable child geometry and simple neighbor relationships. It is well suited to data whose resolution is naturally spatial, such as pixels and voxels. However, it can waste space when objects are concentrated in a small region or when the world contains large empty areas. Loose quadtrees and loose octrees reduce duplication by allowing an object to be associated with a node whose expanded region contains it.

A quadtree's depth depends on coordinate range and resolution. If a square region has side length L and subdivision continues to cell width r, the approximate depth is

where L and r use the same length units. This is a resolution relationship, not a guarantee of balanced storage, because occupied data may be distributed unevenly.

4. R-Trees

An R-tree is a height-balanced index for rectangles, rectangles in higher dimensions, or other objects represented by minimum bounding rectangles (MBRs). Each node stores entries of the form (MBR, child pointer) for internal nodes or (MBR, object identifier) for leaf nodes. A parent MBR encloses all child MBRs.

R-trees are designed for dynamic collections of spatial objects, especially GIS features such as roads, buildings, parcels, and administrative regions. Unlike a k-d tree, an R-tree can index objects with area or volume rather than only points.

4.1 Search

For an intersection query, the algorithm visits a child whenever the query region intersects the child's MBR. If several MBRs overlap, several branches may be searched. At a leaf, the actual geometry should be tested because an MBR intersection is only a candidate condition.

This two-stage process is called filter and refine:

1. Filter: use bounding boxes to produce candidates.
2. Refine: apply exact geometric predicates to candidates.

The same strategy applies to distance queries, containment tests, and spatial joins.

4.2 Insertion and node splitting

An R-tree chooses a leaf whose MBR requires the least enlargement to contain the new object. If the leaf overflows, its entries are split into two groups. The split aims to minimize wasted area, overlap, or perimeter, depending on the algorithm. Classical R-trees use heuristics; R*-trees improve reinsertion and split policies; bulk-loaded variants are often better for static datasets.

Overlap between sibling MBRs is a central performance issue. When overlap is high, a query cannot determine which branch contains a result and must explore many branches. Data distribution, insertion order, split strategy, and page capacity all influence overlap.

4.3 R-tree variants

• R-tree: general dynamic bounding-rectangle index.
• R*-tree: improves area, margin, and overlap behavior through refined splitting and reinsertion.
• R+-tree: attempts to avoid overlap, sometimes duplicating objects across nodes.
• Bulk-loaded R-tree: builds the index from an organized dataset and is effective for read-heavy workloads.
• 3D and spatiotemporal R-trees: extend bounding regions to volume or time-space dimensions.

R-trees are not automatically ideal for every spatial workload. They may perform poorly when objects have very large extents, when MBRs overlap heavily, or when the query workload is dominated by exact nearest-neighbor searches on points.

5. Spatial Hashing and Uniform Grids

Spatial hashing maps a spatial cell to a hash-table bucket. Space is divided into cells of width s, and a point with coordinates (x,y) is assigned to integer cell coordinates

For three dimensions, the key is (⌊x/s⌋,⌊y/s⌋,⌊z/s⌋). A hash function maps this integer tuple to a table position. The table stores object identifiers associated with that cell.

For a point query, the relevant cell is examined. For a range or proximity query, the algorithm examines the query cell and neighboring cells whose regions could intersect the query. A radius-r query may require approximately (2⌈r/s⌉+1)^k cells in a regular k-dimensional grid, although boundary geometry and sparse hashing change the exact count.

5.1 Choosing cell size

Small cells reduce the number of candidates per cell but increase the number of neighboring cells and metadata. Large cells reduce metadata but increase candidate testing. A useful choice depends on object density, query radius, and motion patterns rather than on a universal rule.

Spatial hashing is especially effective for dynamic simulations and collision detection, where objects move frequently and exact balance is less important than fast insertion and neighborhood access. It is weaker for highly nonuniform data if a fixed grid creates very crowded cells.

5.2 Hashing concerns

A spatial hash must handle negative coordinates consistently. Floor division and truncation toward zero are not equivalent for negative values. Integer overflow, poor hash mixing, and excessive collisions can also degrade performance. Open addressing and chaining are common collision-resolution methods, but the implementation should distinguish spatial-cell collisions from geometric collisions.

6. Dimensionality and the Curse of Dimensionality

The phrase curse of dimensionality describes several related effects. In a unit hypercube, if a query examines a fraction r of each coordinate range, the fraction of volume is r^k. For r = 0.1, this is 0.1 in one dimension, 0.01 in two dimensions, and 0.000001 in six dimensions. Conversely, to capture a fixed fraction of volume, a region must become broad in many coordinates.

Distances also concentrate in high dimensions for many data distributions. The ratio between nearest and farthest distances may shrink, making nearest-neighbor distinctions less meaningful and weakening geometric pruning. The exact behavior depends on the distribution, metric, scaling, and intrinsic dimension; it is not a universal theorem that all high-dimensional data become unusable.

Practical consequences include:

• k-d trees visit a larger fraction of nodes.
• Grid methods require many neighboring cells.
• R-tree bounding boxes become less selective.
• Memory for regular subdivisions grows as 2^k per level.
• Feature scaling becomes critical because one coordinate can dominate distance.

For high-dimensional feature vectors, approximate nearest-neighbor methods, dimensionality reduction, metric learning, or inverted indexes may be more appropriate than classical spatial structures. Principal component analysis, random projections, product quantization, and graph-based indexes are possible alternatives, but each changes the accuracy, metric, or storage trade-off.

7. Comparative Selection Framework

Selection should consider more than asymptotic complexity. Important engineering variables include data distribution, query selectivity, object extent, update-to-query ratio, concurrency, persistence, memory locality, parallelism, and the cost of exact geometry refinement.

8. Worked Example: Grid-Based Neighborhood Search

Assume a two-dimensional simulation uses cell size s = 2 m and asks for all objects within radius r = 3 m of a query point. The number of cell indices that may be relevant along one axis is

2⌈r/s⌉+1 = 2⌈3/2⌉+1 = 5.

Thus, a conservative square neighborhood contains 5 × 5 = 25 cells. The circular query actually intersects fewer or equal cells depending on the query's position relative to cell boundaries, but examining the 25-cell neighborhood guarantees that no candidate is missed. Exact Euclidean distance must then be checked for every candidate because cell membership is only a filter.

The example illustrates two design choices. If s is increased to 3 m, the conservative neighborhood becomes 3 × 3 = 9 cells, but each cell contains more objects. If s is decreased to 1 m, the neighborhood becomes 7 × 7 = 49 cells, but each cell is less crowded. The best choice depends on density and the relative cost of cell access versus distance testing.

9. Applications

9.1 GIS

GIS databases use R-trees and related indexes for spatial joins, map rendering, intersection tests, and proximity searches. A query such as “parcels intersecting a flood zone” first compares parcel MBRs with the flood-zone MBR, then applies exact polygon intersection. Coordinate reference systems must be chosen carefully. Distances in degrees are not generally distances in meters, and dateline or polar behavior can invalidate naïve bounding boxes.

Spatial indexes also support temporal extensions. A moving vehicle trajectory may be indexed by a three-dimensional box with longitude, latitude, and time, though specialized trajectory indexes may be more suitable.

9.2 Robotics

Robotic mapping commonly uses occupancy grids, quadtrees, or octrees. A mobile robot updates cells using sensor rays and queries nearby occupied cells for collision checking. An octree can represent a large three-dimensional environment at coarse resolution while refining only near surfaces.

Motion planning often uses a broad-phase collision structure to identify possible obstacles, followed by narrow-phase geometric tests. Dynamic obstacles create update pressure, making spatial hashing, bounding-volume hierarchies, or incremental trees attractive.

9.3 Computer Vision

Image pyramids and quadtrees support adaptive segmentation, region homogeneity tests, and variable-resolution processing. A quadtree may subdivide an image until each block meets a texture or variance criterion. For local feature matching, however, the descriptor dimension may be high; k-d trees are useful for moderate-dimensional approximate search, while more specialized methods are often needed for modern deep feature vectors.

9.4 Scientific Computing

Particle simulations require repeated neighborhood queries. Uniform grids and spatial hashing provide efficient short-range interaction lookup when particle density is approximately uniform. Adaptive octrees support N-body approximations, adaptive mesh refinement, and visualization of large volumetric datasets. In adaptive mesh refinement, fine cells are concentrated where gradients or physical complexity are high, reducing computation compared with a uniformly fine mesh.

10. Applied Case: Illustrative Urban Emergency-Response System

Background

Consider an illustrative city emergency-response platform containing ambulance locations, hospitals, road segments, traffic incidents, and flood polygons. The system must answer proximity, intersection, and route-obstacle queries while receiving frequent vehicle and incident updates.

Problem

A single index is unlikely to serve all object types efficiently. Ambulances are moving points; hospitals are points with attributes; roads are polylines; flood zones are polygons; and the city boundary is large but unevenly populated. Response time is important, but results must also be geographically valid.

Analysis

A k-d tree could support static hospital nearest-neighbor queries, but repeated ambulance updates would require rebuilding or accepting imbalance. An R-tree is appropriate for roads, flood polygons, and hospitals represented by bounding boxes. A spatial hash is attractive for rapidly changing ambulance positions and local vehicle proximity. If elevation and three-dimensional building geometry matter, an octree can support local collision or visibility analysis.

Approach / Solution

The system uses a hybrid architecture:

1. An R*-tree indexes roads, hospitals, and flood polygons.
2. A spatial hash stores current ambulance positions in cells selected according to typical dispatch radius.
3. A cached or periodically rebuilt k-d tree supports read-heavy nearest-hospital analysis.
4. Candidate results from bounding boxes or cells undergo exact geodesic, polyline, or polygon tests.
5. All records retain coordinate-reference metadata, timestamps, and data-quality flags.

A nearest hospital is not selected solely by straight-line distance. The system first obtains spatial candidates, then considers road-network travel time, traffic, hospital capacity, and accessibility constraints.

Outcome

The hybrid design separates update-heavy and query-heavy workloads, reduces unnecessary geometric tests, and allows each structure to exploit the geometry of its data. It also makes performance monitoring more interpretable: poor results can be traced to hash-cell density, R-tree overlap, stale k-d-tree rebuilds, or expensive route calculations.

Learning Points

• No single spatial structure dominates across object types.
• Bounding-box filtering must be followed by exact refinement.
• Coordinate systems and timestamps are part of correctness, not merely metadata.
• Operational decisions require semantic attributes in addition to geometric proximity.
• Hybrid indexing is often superior to forcing all data into one structure.

11. Implementation and Engineering Best Practices

1. Define the metric explicitly. Euclidean, Manhattan, geodesic, and application-specific distances produce different neighbors.
2. Normalize or transform coordinates when appropriate. Avoid mixing meters, degrees, pixels, and normalized features without justification.
3. Use stable boundary conventions. Half-open grid cells can prevent duplicate assignment at shared boundaries.
4. Separate candidate generation from exact testing. Bounding boxes and cells are filters, not proofs of geometric intersection.
5. Measure real workloads. Report build time, memory, update latency, query latency, candidate counts, and tail percentiles.
6. Test adversarial distributions. Include clustered, diagonal, duplicate, skewed, empty, and highly overlapping datasets.
7. Rebuild or rebalance when necessary. Dynamic updates can degrade trees even when individual operations appear inexpensive.
8. Exploit memory locality. Array-based layouts, packed nodes, and cache-aware traversal can matter more than asymptotic notation.
9. Use approximate methods transparently. Record error bounds, recall, and the conditions under which approximation is acceptable.
10. Protect spatial data. Location information can identify individuals, sensitive facilities, or vulnerable populations.

12. Limitations, Ethics, and Governance

Spatial indexing can expose sensitive information even when names are removed. A sequence of location points may re-identify a person through home, workplace, or routine patterns. Governance should therefore address purpose limitation, access control, retention, encryption, auditability, and aggregation or perturbation where appropriate.

Spatial masking can reduce precision but may also introduce bias. For example, coarse aggregation can disproportionately obscure rural communities or misrepresent small neighborhoods. Differential privacy and spatial k-anonymity may help in some reporting contexts, but they involve accuracy trade-offs and must be evaluated against the risk model.

Algorithmic decisions based on spatial proximity can reproduce unequal access if historical data reflects infrastructure gaps or discriminatory allocation. A technically efficient nearest-neighbor query is not automatically a fair resource-allocation policy. Systems used in emergency response, policing, insurance, or public services require human oversight, documented decision rules, and impact evaluation.

13. Contemporary Developments and Research Directions

Current research combines classical spatial indexes with learned models, GPUs, distributed systems, and approximate search. Learned spatial indexes attempt to predict the position of a key or region in an ordered representation, but their benefit depends on data stability and the cost of handling prediction error. GPU-based uniform grids and hierarchical structures accelerate massively parallel collision and particle workloads. Distributed spatial databases partition data by space, using replication or carefully chosen boundaries to avoid excessive cross-partition queries.

Spatiotemporal indexing is increasingly important for mobility, climate, remote sensing, and sensor networks. The additional time dimension can increase overlap and dimensionality, so workload-specific designs are essential. AI systems also create high-dimensional embeddings whose “spatial” searches often require approximate nearest-neighbor graphs rather than geometric partition trees. The conceptual lessons remain the same: define a metric, exploit locality, quantify approximation, and validate on the actual distribution.

Chapter Summary

Spatial and multidimensional data structures organize points, regions, and volumes so that geometric queries can prune irrelevant data. k-d trees use recursive binary hyperplanes and are effective for low-dimensional point queries, especially nearest-neighbor search. Quadtrees and octrees recursively subdivide space into four or eight regions and are natural for images, occupancy maps, voxels, and adaptive resolution. R-trees index extended objects through hierarchical minimum bounding rectangles and are central to dynamic GIS workloads. Spatial hashing and uniform grids provide simple, fast neighborhood access for highly dynamic or approximately uniform simulations.

No structure is universally best. Dimensionality, data distribution, object size, update rate, query selectivity, memory locality, and metric choice determine performance. Bounding-box or cell filtering normally requires exact refinement. In high dimensions, classical pruning weakens and approximate or specialized indexes may be preferable. Practical systems often combine several structures, while governance must address coordinate correctness, privacy, fairness, and auditability.

Key Terms

Spatial index: A data structure that accelerates queries involving geometric location or extent.

k-d tree: A binary tree that recursively partitions k-dimensional space by coordinate hyperplanes.

Quadtree: A two-dimensional hierarchical structure that subdivides a region into four quadrants.

Octree: A three-dimensional hierarchical structure that subdivides a volume into eight octants.

R-tree: A height-balanced tree that indexes objects using hierarchical minimum bounding rectangles.

Spatial hashing: Mapping spatial cells to hash-table buckets for fast neighborhood access.

Uniform grid: A regular partition of space into equal-sized cells.

Minimum bounding rectangle (MBR): The smallest axis-aligned rectangle enclosing an object.

Range query: A query reporting objects within a specified region.

Nearest-neighbor query: A query finding the object closest to a specified point under a chosen metric.

Bounding box: An axis-aligned region used to approximate an object for filtering.

Filter and refine: A two-stage process using approximate bounds followed by exact geometry tests.

Curse of dimensionality: Performance degradation caused by increasing dimensionality.

Spatial locality: The tendency of nearby data to be accessed or related together.

Occupancy map: A representation labeling spatial cells as free, occupied, or unknown.

Adaptive subdivision: Refining only regions requiring greater spatial resolution.

Node overlap: Intersection between bounding regions stored in sibling index nodes.

Spatial join: Combining records according to a geometric relationship.

Coordinate reference system: A defined system for interpreting spatial coordinates and units.

Approximate nearest-neighbor search: A method trading exactness for improved speed or scalability.

Review Questions

Short Answer Questions

1. What is the principal difference between a k-d tree and a quadtree?
2. Why must an R-tree intersection query usually perform an exact refinement step?
3. Define the curse of dimensionality in the context of spatial search.
4. What role does cell size play in spatial hashing?
5. Why are coordinate reference systems important in GIS distance queries?

Long Answer Questions

1. Explain the construction, range-search procedure, nearest-neighbor procedure, and limitations of a balanced k-d tree.
2. Compare quadtrees, octrees, and uniform grids for representing occupancy in robotics.
3. Describe R-tree insertion, node splitting, overlap, and the filter-and-refine query model.
4. Analyze how dimensionality affects k-d trees, regular grids, and R-trees.
5. Develop a selection framework for choosing among a k-d tree, R-tree, octree, and spatial hash in a production system.

Analytical / Application Questions

1. Design a hybrid spatial indexing architecture for a GIS containing moving vehicles, roads, buildings, and time-stamped incidents. Justify each structure.
2. A particle simulation has highly uniform density and frequent short-range interaction queries. Compare two possible cell sizes for a spatial hash and specify the measurements needed to select between them.
3. A nearest-neighbor system uses latitude and longitude directly with Euclidean distance. Identify the correctness risks and propose a technically sound replacement strategy.

Multiple Choice Questions with Answers

Question 1

Which structure recursively divides two-dimensional space into four regions?

A. Quadtree

B. R-tree

C. k-d tree

D. Spatial hash

Correct Answer: A. Quadtree

Question 2

What does an R-tree primarily store at internal nodes?

A. Sorting keys only

B. Minimum bounding rectangles and child pointers

C. Hash codes without geometry

D. Exact polygon boundaries only

Correct Answer: B. Minimum bounding rectangles and child pointers

Question 3

For a k-d-tree nearest-neighbor search, when may a subtree be safely pruned?

A. Whenever its split coordinate is opposite the query point

B. Whenever it contains more than one point

C. When its distance lower bound is no smaller than the current best distance

D. Only when the subtree is a leaf

Correct Answer: C. When its distance lower bound is no smaller than the current best distance

Question 4

In a two-dimensional spatial hash with cell width s, which expression gives the cell indices for point (x,y)?

A. (x/s, y/s) without rounding

B. (⌊x/s⌋, ⌊y/s⌋)

C. (s/x, s/y)

D. (x−s, y−s)

Correct Answer: B. (⌊x/s⌋, ⌊y/s⌋)

Question 5

An octree divides each node into how many children in its standard three-dimensional form?

A. 4

B. 6

C. 8

D. 16

Correct Answer: C. 8

Question 6

Why can high dimensionality weaken spatial indexing?

A. All distances become exactly zero

B. More index branches or cells may intersect a query, reducing pruning

C. Hash tables cannot store integers

D. Bounding boxes cease to exist

Correct Answer: B. More index branches or cells may intersect a query, reducing pruning

Question 7

A GIS query first tests MBR overlap and then tests exact polygon intersection. What is this process called?

A. Filter and refine

B. Median balancing

C. Lazy deletion

D. Coordinate quantization

Correct Answer: A. Filter and refine

Question 8

For a grid cell size of 2 m and query radius of 3 m, what conservative number of cells per axis should be examined using 2⌈r/s⌉+1?

A. 3

B. 4

C. 5

D. 6

Correct Answer: C. 5

Question 9

Which structure is generally most appropriate for dynamic collections of rectangles and polygons?

A. R-tree

B. Plain sorted array

C. Stack

D. Binary heap

Correct Answer: A. R-tree

Question 10

Why should Euclidean distance generally not be applied directly to latitude and longitude over large geographic areas?

A. Latitude and longitude are always integers

B. Geographic coordinates represent a curved surface and angular units

C. R-trees cannot index points

D. Longitude has no ordering

Correct Answer: B. Geographic coordinates represent a curved surface and angular units