Computers have gotten so fast at finding the best route on a map that it basically costs them zero effort now, no matter how big the city.
March 30, 2026
Original Paper
Distances in Planar Graphs are Almost for Free!
arXiv · 2603.26313
The Takeaway
For decades, mathematicians believed there was a fundamental trade-off: you could either have a lightning-fast search or a small file size, but not both. This paper proves you can have both simultaneously, allowing for nearly instant navigation calculations on complex networks while using almost no memory.
From the abstract
We prove that, up to subpolynomial or polylogarithmic factors, there is no tradeoff between preprocessing time, query time, and size of exact distance oracles for planar graphs. Namely, we show how given an $n$-vertex weighted directed planar graph $G$, one can compute in $n^{1+o(1)}$ time and space a representation of $G$ from which one can extract the exact distance between any two vertices of $G$ in $\log^{2+o(1)}(n)$ time. Previously, it was only known how to construct oracles with these spa