Approximate Distance Oracles for Planar Graphs with Subpolynomial Error Dependency

Thorup [FOCS'01, JACM'04] and Klein [SODA'01] independently showed that there exists a (1 + )-approximate distance oracle for planar graphs with O(n(log n) -1 ) space and O( -1 ) query time. While the dependency on n is nearly linear, the space-query product of their oracles depend quadratically on 1 . Many follow-up results either improved the space or the query time of the oracles while having the same, sometimes worst, dependency on 1 . Kawarabayashi, Sommer, and Thorup [SODA'13] were the first to improve the dependency on 1 from quadratic to nearly linear (at the cost of log * (n) factors). It is plausible to conjecture that the linear dependency on 1 is optimal: for many known distance-related problems in planar graphs, it was proved that the dependency on 1 is at least linear.

In this work, we disprove this conjecture by reducing the dependency of the space-query product on 1 from linear all the way down to subpolynomial (1 ) o(1) . More precisely, we construct an oracle with O(n log(n)( -o(1) + log * n)) space and log 2+o(1) (1 ) query time. Our construction is the culmination of several different ideas developed over the past two decades.