Scalable Ultrafast Almost-optimal Euclidean Shortest Paths

Stefan Funke, Daniel Koch, Claudius Proissl, Axel Schneewind, Armin Weiß, Felix WeitbrechtIJCAI 2024

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 Euclidean Shortest Path Problem involves finding the shortest path (solid green) between points s and t while avoiding obstacles.

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.

Comparison of a standard navigation mesh (left) versus the refined discretization (right) using Steiner points to improve triangle quality for complex coastlines.

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

BibTeX
@inproceedings{funke2024scalable,
  author = {Stefan Funke and Daniel Koch and Claudius Proissl and Axel Schneewind and Armin Weiß and Felix Weitbrecht},
  title = {{Scalable Ultrafast Almost-optimal Euclidean Shortest Paths}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2024},
}
Figure