Introduction
The Euclidean Shortest Path Problem (ESPP) is a fundamental challenge in computational geometry: finding the shortest route between two points in a 2D plane while navigating around polygonal obstacles. While theoretically well-understood, scaling ESPP solutions to massive, real-world datasets—such as global coastline maps with millions of vertices—presents significant engineering hurdles.
The Challenge of Scale
Existing approaches often struggle with "planet-sized" data. Visibility graphs, which connect all mutually visible obstacle vertices, grow quadratically ($O(n^2)$), making them memory-prohibitive for large datasets. Continuous Dijkstra algorithms are optimal but complex and slow in practice. Modern navigation meshes, like those used by Polyanya, utilize A* search but lack the heavy precomputation needed for millisecond-level queries on complex maps.
The authors' goal was to develop a solution that offers ultrafast queries (milliseconds) on massive scales (millions of vertices) with near-optimal results.
Methodology: Adapting Contraction Hierarchies
Researchers from the University of Stuttgart have introduced a high-performance pipeline that adapts "Contraction Hierarchies" (CH)—a technique originally designed for lightning-fast road network routing—to the geometric domain of ESPP. Their approach consists of four primary stages:
1. Refined Discretization
The process begins with a Constrained Delaunay Triangulation (CDT) of the obstacles. To ensure high path quality and efficient search, the authors use Ruppert’s algorithm to insert Steiner points. This creates a "well-shaped" navigation mesh, avoiding the "skinny" triangles that typically degrade performance in geometric search.
2. Shortcut-Optimized Contraction Hierarchies (SO-CH)
The core innovation lies in applying CH to the mesh edges. By "contracting" nodes and adding "shortcuts" that preserve shortest distances, the system builds a hierarchical index. In their Shortcut-Optimized CH (SO-CH), if a shortcut's endpoints are mutually visible, its weight is updated to the direct Euclidean distance. This effectively "bakes" visibility-based optimization into the precomputed index.
3. Path Optimization via the Funnel Algorithm
Because paths on a mesh are initially constrained to edges, a post-processing step is required. The Funnel Algorithm "tightens" the path within the sequence of triangles identified by the CH query, resulting in a smooth, nearly optimal Euclidean path.
Experimental Results
The authors evaluated their system using global geographic data from OpenStreetMap (OSM), including a "Planet" dataset featuring 15.4 million vertices.
- Query Speed: On the full Planet dataset, the system achieved an average query time of just 1.37 milliseconds. This is orders of magnitude faster than standard Dijkstra (3+ seconds) and significantly outperforms state-of-the-art tools like Polyanya, which exceeded memory limits on the same hardware.
- Path Quality: The results are nearly optimal. On datasets with known optima, paths were within 0.1% of the true shortest distance. On the global dataset, paths remained within 1.6% of a theoretical lower bound.
- Scalability: Despite the massive scale, the system operates within 64GB of RAM, making it feasible for high-end workstations.
Conclusion
By combining geometric refinement with hierarchical graph techniques, this research demonstrates that "planet-scale" Euclidean shortest path queries can be answered in milliseconds. While currently limited to 2D environments and requiring significant initial preprocessing time (approx. 30–40 minutes for the global map), the approach sets a new benchmark for performance and scalability in geometric routing.
Reference: Funke, S., et al. (2024). Scalable Ultrafast Almost-optimal Euclidean Shortest Paths. Proceedings of the 33rd International Joint Conference on Artificial Intelligence (IJCAI-24).
Summary updated