论文标题
平面距离甲骨文具有更好的时间空间权衡
Planar Distance Oracles with Better Time-Space Tradeoffs
论文作者
论文摘要
在最近的突破中，Charalampopoulos，Gawrychowski，Mozes和Weimann（Stoc 2019）表明，可以通过$ n^{o（1）$ nime（$ n^{1+o（1+o（1+o（1+o（1）$ o（$ o o o o o o o o（1），$ o（1），$ o（1）$（1）$ o（1）$（1）$（1）$（1）$（1）$（1），可以在平面图上的确切距离查询。可以同时实现。它们的距离查询算法是递归的：它连续调用平面Voronoi图的点位置算法，其中涉及许多递归距离查询。此递归的深度是非恒定的，并且分支因子对数，导致$（\ log n）^{ω（1）} = n^{o（1）} $查询时间。 在本文中，我们提出了一种在平面Voronoi图中进行点位置的新方法，该图导致了新的确切距离甲骨文。在我们时空权衡曲线的两个极端，我们可以实现 $ n^{1+o（1）} $ space和$ \ log^{2+o（1）} n $查询时间，或 $ n \ log^{2+o（1）} n $ space和$ n^{o（1）} $查询时间。 所有以前的牙齿都带有$ \ tilde {o}（1）$查询时间占用空间$ n^{1+ω（1）} $，以及所有以前的带有空间$ \ tilde {o}（o}（o}（n）$答案查询$ n^{ω（1）} $ time。
In a recent breakthrough, Charalampopoulos, Gawrychowski, Mozes, and Weimann (STOC 2019) showed that exact distance queries on planar graphs could be answered in $n^{o(1)}$ time by a data structure occupying $n^{1+o(1)}$ space, i.e., up to $o(1)$ terms, optimal exponents in time (0) and space (1) can be achieved simultaneously. Their distance query algorithm is recursive: it makes successive calls to a point-location algorithm for planar Voronoi diagrams, which involves many recursive distance queries. The depth of this recursion is non-constant and the branching factor logarithmic, leading to $(\log n)^{ω(1)} = n^{o(1)}$ query times. In this paper we present a new way to do point-location in planar Voronoi diagrams, which leads to a new exact distance oracle. At the two extremes of our space-time tradeoff curve we can achieve either $n^{1+o(1)}$ space and $\log^{2+o(1)}n$ query time, or $n\log^{2+o(1)}n$ space and $n^{o(1)}$ query time. All previous oracles with $\tilde{O}(1)$ query time occupy space $n^{1+Ω(1)}$, and all previous oracles with space $\tilde{O}(n)$ answer queries in $n^{Ω(1)}$ time.
