What question did this study set out to answer?

To establish the preprocessing requirements for distance oracles in n×n grid graphs under the Strong Exponential Time Hypothesis.

February 8, 2026Open Access

Conditional Lower Bounds for Grid Pathfinding Oracles

Key Points

To establish the preprocessing requirements for distance oracles in n×n grid graphs under the Strong Exponential Time Hypothesis.
Proved through reduction from the Orthogonal Vectors problem
Used explicit gadget construction to demonstrate the bounds
Any distance oracle requires Ω(n^(2-o(1))) preprocessing time
Achieving O(1) query time is expensive in terms of preprocessing
Provides justification for algorithms like Jump Point Search with O(n²) preprocessing and O(path length) query time

Abstract

This paper proves that, assuming the Strong Exponential Time Hypothesis (SETH), any distance oracle for n×n grid graphs with O (1) query time requires Ω (n^ (2-o (1) ) ) preprocessing time. The proof proceeds by reduction from the Orthogonal Vectors (OV) problem via an explicit gadget construction. The main result establishes a fundamental space-time tradeoff: achieving constant-time distance queries on grids is provably expensive in preprocessing. This provides theoretical justification for the design of practical pathfinding algorithms like Jump Point Search (JPS+), which achieve O (n²) preprocessing with O (path length) query time.

AIに質問

Bookmark

View Full Paper