Approximate Distance Oracles for Planar Graphs with Subpolynomial Error Dependency
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 …