Computational Geometry and Spatial Data Structures

Introduction

Computational geometry studies algorithms for objects represented by points, line segments, polygons, curves, and regions. Spatial data structures organize these objects so that geometric queries can be answered efficiently. Together, they support geographic information systems (GIS), robotics, computer graphics, computer-aided design, location analytics, simulation, and visualization.

A central difficulty is that spatial data are multidimensional and often involve relationships such as intersection, containment, proximity, visibility, and order. Scanning every object for every query is usually unacceptable. If a dataset contains n objects and a query examines all of them, the cost is typically O(n) per query. Preprocessing and indexing can reduce this cost substantially, although construction time, memory consumption, update cost, and worst-case behavior must be considered.

This chapter develops geometric predicates, convex hulls, sweep-line algorithms, range searching, k-d trees, quadtrees, and nearest-neighbour search. It also evaluates their use in a realistic location-analytics application.

Learning Objectives

After completing this chapter, the reader should be able to:

1. Apply orientation, distance, intersection, and containment predicates reliably.
2. Construct and analyse convex hull algorithms.
3. Explain sweep-line processing and event ordering.
4. Select and use spatial indexes, including k-d trees and quadtrees.
5. Design range and nearest-neighbour queries with pruning.
6. Evaluate exactness, performance, numerical robustness, and update behaviour.
7. Apply spatial algorithms to GIS, robotics, visualization, and location analytics.

1. Geometric Foundations

A point in d-dimensional Euclidean space is represented as p = (p₁, p₂, …, p_d). Most introductory algorithms operate in two dimensions, where p = (x, y). A geometric object may be a point, segment, polyline, polygon, rectangle, circle, or a collection of such objects.

1.1 The orientation predicate

For three planar points a, b, and c, define the signed cross product:

The value is positive when c lies to the left of directed edge ab, negative when it lies to the right, and zero when the points are collinear. Its units are squared coordinate units, such as m² if coordinates are measured in metres.

Orientation is the foundation of convex-hull construction, segment intersection, polygon orientation, and many visibility tests. The predicate assumes a consistent Cartesian coordinate system. In geographic longitude–latitude coordinates, direct planar use becomes inaccurate over large areas because the Earth is curved; projected coordinates or geodesic methods should then be used.

1.2 Distance

For points p and q in Euclidean d-space, the L₂ distance is:

The squared distance,

is preferable when only comparisons are required, because it avoids the square-root operation. The formula assumes Euclidean geometry and coordinates with compatible units.

For a point p and axis-aligned rectangle R = [x_min, x_max] × [y_min, y_max], the minimum squared distance is found by clamping each coordinate to the rectangle. Let qₓ be xₓ clamped to the interval [x_min, x_max], and qᵧ similarly. Then:

This lower bound is crucial for pruning spatial indexes.

1.3 Segment intersection

Two closed segments ab and cd intersect if their orientations indicate that each segment straddles the line containing the other, with special handling for collinear endpoints and overlapping intervals. A robust implementation must explicitly test zero-orientation cases. Floating-point equality to zero is unsafe for nearly collinear data; exact integer arithmetic, adaptive predicates, or a documented tolerance policy is preferable.

2. Convex Hulls

The convex hull of a finite point set P is the smallest convex set containing every point in P. In two dimensions it can be visualized as a taut elastic band around the points. Hull vertices are useful for collision detection, shape simplification, spatial summarization, and robotics.

2.1 Graham scan

Graham scan selects a pivot, usually the lowest y-coordinate point with a tie-breaking lowest x-coordinate, sorts the other points by polar angle around the pivot, and scans them using a stack. For each new point, points are removed while the last two stack points and the new point do not make the required counterclockwise turn.

With n points, sorting costs O(n log n), and the scan costs O(n), giving total time O(n log n) and auxiliary space O(n). Collinear boundary points require a policy: retain only extreme endpoints, or retain every boundary point. The chosen policy must be stated because it changes the output hull.

2.2 Andrew’s monotone chain

The monotone-chain algorithm sorts points lexicographically by (x, y), constructs a lower hull and an upper hull, and concatenates them. It is often easier to implement robustly than angle sorting. Its time complexity is O(n log n), dominated by sorting; the scan itself is linear.

Worked example: orientation in a hull scan

Let a = (1, 1), b = (4, 2), and c = (3, 5). Then:

orient(a,b,c) = (4 − 1)(5 − 1) − (2 − 1)(3 − 1) = 3×4 − 1×2 = 10.

Because 10 > 0, c is to the left of ab, so the turn is counterclockwise. A positive result is not a distance; it is twice the signed area of triangle abc.

3. Sweep-Line Methods

A sweep-line algorithm conceptually moves a vertical line across the plane. Events occur when the line reaches an object endpoint, vertex, or query boundary. The algorithm maintains an ordered status structure containing objects currently intersected by the sweep line.

For n segments, the Bentley–Ottmann approach reports all k intersections in O((n + k) log n) time under standard assumptions, with O(n + k) output-sensitive space. The event queue contains segment endpoints and discovered intersection events; the status structure orders active segments by their vertical position at the current sweep coordinate.

Only neighbouring segments in the status structure need to be tested after an insertion, deletion, or crossing. This locality is the reason the method avoids testing all O(n²) segment pairs. However, event ordering is delicate: coincident endpoints, overlapping segments, and multiple segments meeting at one point require explicit tie-breaking and event aggregation.

Sweep-line methods are used for map-overlay operations, line-intersection detection, polygon clipping, visibility computation, and detecting conflicting road or utility segments. Their complexity assumes a comparison-based ordered structure and general-position conditions unless degeneracies are handled.

4. Range Searching and Spatial Indexes

A range query returns all objects satisfying a spatial condition. For example, an orthogonal range query in two dimensions returns points in rectangle R = [x₁, x₂] × [y₁, y₂]. If k points are reported, query complexity should include output size: O(log n + k) is a desirable target for several static structures, although exact bounds depend on the structure and dimension.

Spatial indexes generally use bounding regions. A minimum bounding rectangle (MBR) is the smallest axis-aligned rectangle containing an object or group of objects. During a query, a node can be rejected when its MBR does not intersect the query region. MBRs accelerate filtering but may overlap, causing multiple branches to be visited.

4.1 k-d trees

A k-d tree recursively partitions k-dimensional space with axis-aligned hyperplanes. At depth d, implementations commonly split using coordinate axis d mod k, or choose the dimension with greatest spread. A balanced tree is often built by selecting a median point, giving approximately O(log n) depth.

For an orthogonal range query, the algorithm recursively visits a subtree only when its bounding region intersects the query rectangle. Fully contained subtrees can sometimes be reported without examining every point. Average performance is often strong for moderate dimensions, but worst-case range queries can approach O(n), particularly with skewed data, poor splits, or high dimensionality.

A standard static nearest-neighbour search maintains the best distance found so far. At each node it visits the likely side first and visits the opposite side only if the distance from the query point to that side’s bounding region is less than the current best distance. The method is exact when the lower-bound test is correct.

4.2 Quadtrees

A quadtree recursively subdivides a two-dimensional region into four equal quadrants. A point quadtree partitions according to stored points; a region quadtree partitions a fixed spatial domain according to data occupancy or image values. Subdivision continues until a capacity, resolution, or homogeneity condition is reached.

Quadtrees are natural for raster maps, collision detection, adaptive visualization, and occupancy grids. Their depth depends on spatial distribution and coordinate resolution. Highly clustered data can produce deep paths, so maximum depth, bucket capacity, and duplicate-coordinate handling must be specified.

4.3 R-trees

R-trees organize rectangles or other spatial objects using hierarchical MBRs. Unlike a basic k-d tree, an R-tree supports dynamic insertion and deletion and can index rectangles, lines, and polygons through their bounding boxes. Search descends into every child whose MBR intersects the query region. Overlapping MBRs may cause several branches to be explored.

R*-trees improve node organization through reinsertion and split heuristics. In practice, R-trees are common in spatial databases because they provide a useful compromise between dynamic updates and multidimensional querying. Their performance is data-dependent rather than guaranteed solely by tree height.

5. Nearest-Neighbour Search

The nearest-neighbour problem asks for an object minimizing distance to a query point q:

For k-nearest neighbours, return the k objects with smallest distances. A brute-force search costs O(nd) for n points in d dimensions. An index can reduce average query work by pruning regions whose lower-bound distance exceeds the current candidate distance.

For approximate nearest-neighbour search, the algorithm may accept a point whose distance is within a factor (1 + ε) of the exact optimum, where ε ≥ 0. Approximation can be valuable in high-dimensional machine-learning or location-recommendation workloads, where exact indexes suffer from the curse of dimensionality. The approximation guarantee must be stated; an arbitrary early termination is not automatically a bounded approximation.

Distance choice is part of the model. Euclidean distance is appropriate for projected planar coordinates, Manhattan distance may model grid movement, and network distance is appropriate for road travel. A nearest facility under Euclidean distance may not be nearest by travel time.

6. Numerical Robustness and Coordinate Reference Systems

Geometric algorithms are unusually sensitive to numerical error. Common problems include nearly collinear points, cancellation in orientation determinants, duplicate vertices, antimeridian crossing, and inconsistent coordinate units.

Best practices include:

• use integer or fixed-point coordinates when precision requirements permit;
• use robust orientation and incircle predicates for critical decisions;
• define whether polygon boundaries are included;
• normalize or validate ring orientation and closure;
• use a suitable projected coordinate reference system for local metric operations;
• use geodesic calculations for global distances when planar error is unacceptable;
• test degeneracies rather than assuming general position.

An index must also preserve the semantics of the source data. A bounding box in longitude–latitude degrees is not a rectangle of equal physical size everywhere, and a degree is not a fixed distance in the north–south and east–west directions.

7. Applied Case: Emergency-Facility Location Analytics

The following is an illustrative case. A metropolitan emergency service wants to identify residents more than eight minutes from an emergency facility and recommend temporary ambulance staging locations.

Background and problem

The service stores facility points, road segments, population centroids, and historical incident locations. A naïve process computes every resident-to-facility distance and then checks every road segment for every proposed route. With millions of records, repeated scans are too slow for interactive planning.

Analysis

Facility points are indexed in a k-d tree for approximate initial proximity screening. Road segments are indexed in an R-tree using their MBRs. Population centroids are grouped in a quadtree for map rendering and density summaries. Because response time depends on road travel rather than straight-line distance, Euclidean nearest neighbours are used only as candidates; final ranking uses a network-routing engine.

Approach

1. Convert local data to a suitable projected coordinate system.
2. Validate points, road geometries, and duplicate records.
3. Use a k-d-tree query to obtain the nearest five facilities for each centroid.
4. Route only those candidates, retaining facilities within the required travel-time threshold.
5. Use an R-tree range query to identify roads and facilities inside a proposed service polygon.
6. Use a quadtree to aggregate uncovered population at several map resolutions.
7. Generate candidate staging regions and evaluate them with network travel times, demand, and operational constraints.

The k-d tree reduces candidate generation, while the R-tree limits geometric processing to objects whose bounding boxes may intersect the region. The final answer remains network-based, so index distance is not mistaken for operational distance.

Outcome

The architecture supports interactive exploratory analysis while preserving an exact routing stage for decisions. It also permits incremental updates: new incidents update demand aggregates, facilities can be inserted into a dynamic spatial database, and periodic rebuilding can restore balance for static point indexes.

Learning points

The most important design decision is not selecting the theoretically fastest structure in isolation. It is matching the index, distance model, update pattern, coordinate system, and accuracy requirement to the application. A spatial index is a candidate generator and filter; it does not automatically solve the domain’s semantic problem.

8. Engineering Design and Implementation Guidance

A practical implementation should separate geometry, indexing, and application logic. Geometry functions should be deterministic and independently tested. Index nodes should store bounding regions and object identifiers rather than duplicating large geometries where possible. Query code should expose whether results are exact, approximate, planar, geodesic, or network-based.

For static data, bulk construction is generally preferable to repeated insertion. For dynamic data, choose a structure with explicit update support and monitor tree quality. Benchmark using representative spatial distributions: uniform, clustered, diagonal, duplicate-heavy, and adversarial cases. Measure preprocessing time, memory, median and tail query latency, number of visited nodes, and result correctness.

Parallelism is useful for batch range queries, tiled raster construction, and independent nearest-neighbour requests. Care is required when updates and queries occur concurrently. Immutable snapshots, versioned indexes, or transactional spatial databases can provide consistent reads.

9. Limitations, Governance, and Contemporary Directions

The curse of dimensionality limits the effectiveness of many spatial trees. As dimension increases, bounding regions overlap in relative volume and pruning becomes weak. Learned indexes and graph-based approximate-neighbour methods are active research areas, but they introduce model-management and approximation concerns.

Spatial data also create privacy risks. Repeated location traces can reveal home, workplace, health visits, or political activity. Systems should apply purpose limitation, access control, retention limits, aggregation, and—where appropriate—differential privacy or spatial anonymization. However, anonymization can be weakened by combining datasets, and coarse aggregation can reduce service equity or analytical validity.

GIS decisions may reproduce historical inequality if demand data reflect unequal reporting or access. Analysts should document data provenance, coordinate transformations, missingness, index approximation, and uncertainty. Automated recommendations should remain auditable, especially when they affect emergency response, policing, housing, or public-resource allocation.

Chapter Summary

Computational geometry supplies reliable predicates and algorithms for reasoning about spatial objects. Orientation supports hulls and intersection tests; distance functions support proximity queries but must match the application’s geometry and semantics. Convex hulls summarize point sets, while sweep-line algorithms exploit event ordering to process intersections efficiently. Spatial indexes reduce search by hierarchically bounding regions. k-d trees are effective for static, low-dimensional point data; quadtrees provide natural two-dimensional decomposition; and R-trees support dynamic GIS objects through bounding rectangles. Exact nearest-neighbour search depends on valid lower bounds, whereas approximate methods trade accuracy for speed. Numerical robustness, coordinate reference systems, degeneracy handling, privacy, and fairness are essential parts of professional spatial-system design.

Key Terms

Orientation predicate: Signed test indicating the turn made by three points.

Convex hull: Smallest convex set containing a point set.

Sweep line: Conceptual line used to process geometric events in sorted order.

Event queue: Ordered collection of endpoints, vertices, or intersections.

Status structure: Ordered set of objects currently intersecting a sweep line.

Range query: Retrieval of objects satisfying a spatial region condition.

MBR: Minimum bounding rectangle enclosing an object or group.

k-d tree: Binary space-partitioning tree for k-dimensional data.

Quadtree: Recursive four-way decomposition of a two-dimensional region.

R-tree: Dynamic hierarchy of spatial objects represented by bounding rectangles.

Nearest neighbour: Object minimizing a specified distance to a query.

Lower bound: Guaranteed minimum possible distance used for pruning.

Pruning: Avoiding exploration of a region that cannot improve the answer.

Degeneracy: Special geometric condition such as collinearity or coincident points.

Coordinate reference system: Definition of coordinates, datum, projection, and units.

Planar distance: Distance computed in a flat coordinate system.

Geodesic distance: Distance measured on a curved Earth model.

Curse of dimensionality: Degradation of index discrimination as dimension grows.

Spatial privacy: Protection against harmful inference from location information.

Review Questions

Short Answer Questions

1. What does the orientation predicate determine?
2. Why is squared distance often used in nearest-neighbour comparisons?
3. What is the role of an MBR in a spatial index?
4. State one strength and one limitation of a quadtree.
5. Why can longitude–latitude coordinates be unsuitable for local metric distance calculations?

Long Answer Questions

1. Explain Andrew’s monotone-chain convex-hull algorithm and analyse its time complexity.
2. Describe the event queue and status structure in a sweep-line intersection algorithm.
3. Compare k-d trees, quadtrees, and R-trees for a dynamic GIS application.
4. Explain exact nearest-neighbour pruning using distances to bounding regions.
5. Discuss numerical robustness practices for production computational-geometry software.

Analytical / Application Questions

1. Design an index strategy for a city map containing moving vehicles, road segments, and raster population data. Justify the structure selected for each data type.
2. An emergency planner ranks facilities by straight-line distance but dispatches vehicles over a road network. Analyse the risks and propose a corrected workflow.
3. A k-d tree performs well on uniform data but poorly on highly clustered data. Explain why, propose construction or query improvements, and identify when an alternative index would be preferable.

Multiple Choice Questions with Answers

Question 1

For three points a, b, and c, a positive value of orient(a,b,c) indicates that c is:

A. To the left of directed edge ab

B. To the right of directed edge ab

C. Exactly coincident with a

D. At maximum Euclidean distance from ab

Correct Answer: A. To the left of directed edge ab

Question 2

What is the typical time complexity of Graham scan for n points?

A. O(n) in all cases

B. O(log n)

C. O(n log n)

D. O(n² log n)

Correct Answer: C. O(n log n)

Question 3

Which structure is especially suitable for dynamically indexing rectangles and polygon bounding boxes?

A. Stack

B. R-tree

C. Binary heap

D. Hash table

Correct Answer: B. R-tree

Question 4

Why can squared Euclidean distance be used instead of Euclidean distance for nearest-neighbour comparisons?

A. It preserves the ordering of nonnegative distances

B. It is always measured in metres

C. It works only for one-dimensional data

D. It eliminates coordinate differences

Correct Answer: A. It preserves the ordering of nonnegative distances

Question 5

In a sweep-line algorithm, the status structure contains:

A. All objects in the database permanently

B. Objects currently intersecting the sweep line

C. Only objects already reported as intersections

D. Only polygon centroids

Correct Answer: B. Objects currently intersecting the sweep line

Question 6

What is the principal decomposition performed by a standard quadtree?

A. Two equal intervals

B. Three triangular regions

C. Four rectangular quadrants

D. Eight three-dimensional cubes

Correct Answer: C. Four rectangular quadrants

Question 7

During exact nearest-neighbour search, a subtree can be pruned when:

A. Its identifier is larger than the query identifier

B. Its lower-bound distance exceeds the current best distance

C. It contains more than one point

D. Its points have integer coordinates

Correct Answer: B. Its lower-bound distance exceeds the current best distance

Question 8

Which distance is most appropriate for ranking emergency facilities when travel time follows roads?

A. Always longitude difference

B. Network travel distance or time

C. Only squared Euclidean distance

D. The number of tree levels

Correct Answer: B. Network travel distance or time

Question 9

What is a major cause of poor spatial-tree performance in high dimensions?

A. Bounding regions become less effective at pruning

B. All points become identical

C. Sorting becomes constant time

D. Orientation predicates disappear

Correct Answer: A. Bounding regions become less effective at pruning

Question 10

Which practice best addresses nearly collinear geometric data?

A. Ignore zero-orientation cases

B. Use robust predicates or exact arithmetic where necessary

C. Replace all coordinates with zero

D. Use a random distance metric

Correct Answer: B. Use robust predicates or exact arithmetic where necessary