Conditional Lower Bounds for Grid Pathfinding Oracles

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.