论文标题
具有地位误差依赖性的平面图的近似距离甲壳
Approximate Distance Oracles for Planar Graphs with Subpolynomial Error Dependency
论文作者
论文摘要
Thorup [focs'01，jacm'04]和克莱因[Soda'01]独立地表明，存在$（1+ε）$ - 带有$ O（n（\ log log n）ε^{ - 1}）平面图的$（1+ε）左右距离甲骨文，$（\ log n）ε^{ - 1}）$（ε^{ - 1}）$ QUERY TIME。虽然对$ n $的依赖性几乎是线性的，但它们的甲壳的空间质量产物二次地依赖于$ 1/ε$。许多后续结果要么改善了空间\ emph {或}在具有相同（有时最糟糕的$ 1/ε$）时，要么的查询时间。 Kawarabayashi，Sommer和Thorup [Soda'13]是第一个提高对$ 1/ε$从二次依赖的依赖性的人（费用为$ \ log^*（n）$ factor）。可以猜想的是，对$ 1/ε$的线性依赖性是最佳的：对于平面图中许多已知的距离有关的问题，证明对$ 1/ε$的依赖至少是线性的。 在这项工作中，我们通过将$ 1/ε$的依赖性从线性到\ emph {subpolynomial} $（1/ε）^{o（1）} $降低了$ 1/ε$的依赖性来反驳这一猜想。更准确地说，我们用$ O（n \ log（n）（ε^{ - o（1）} + \ log^*n））$ o Space和$ \ log^{2 + o（1）}（1/ε）$查询时间。我们的建设是在过去二十年中发展的几种不同思想的结晶。
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 \emph{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 \emph{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.
