2022/07/12 by Le, Hung · 1 citation
#Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2207.05659
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(nlog(n)(ε-o(1) + log^*n)) space and log2+o(1)(1/ε) query time. Our construction is the culmination of several different ideas developed over the past two decades.