Almost Optimal Exact Distance Oracles for Planar Graphs
Almost Optimal Exact Distance Oracles for Planar Graphs
复制标题
平面图的近乎最优精确距离预言
DOI：
10.1145/3580474
复制
发表时间：
2023
影响因子：
2.5
通讯作者：
Wulff-Nilsen, Christian
中科院分区：
文献类型：
--
作者：
Charalampopoulos, Panagiotis;Gawrychowski, Paweł;Long, Yaowei;Mozes, Shay;Pettie, Seth;Weimann, Oren;Wulff-Nilsen, Christian
我们考虑的问题，预处理的加权有向平面图，以快速回答精确的距离查询。这个问题的主要矛盾在于空间与查询时间Q之间的矛盾，自20世纪90年代中期以来，所有结果都有多项式时空权衡，例如，Q= ~ Θ（n/S）或Q = ~Θ（n ~ 5/2/S ~ 3/2）.本文证明了在时间和空间之间不存在多项式折衷，并且有可能同时达到几乎最优的空间1 +o（1）和几乎最优的查询时间no（1）.更准确地说，我们实现了以下时空权衡：n1+o（1）空间和log 2 +o（1）n查询时间，nlog 2 +o（1）n空间和no（1）查询时间，n4/3+o（1）空间和log 1 +o（1）n查询时间，我们减少了距离查询的各种点定位问题的加性加权Voronoi图和开发新的算法，点定位问题本身使用几个部分持久的动态树数据结构。
We consider the problem of preprocessing a weighted directed planar graph in order to quickly answer exact distance queries. The main tension in this problem is betweenspaceSandquery timeQ, and since the mid-1990s all results had polynomial time-space tradeoffs, e.g.,Q= ~ Θ(n/√ S) orQ= ~Θ(n5/2/S3/2).In this article we show that there is no polynomial tradeoff between time and space and that it is possible tosimultaneouslyachieve almost optimal spacen1+o(1)and almost optimal query timeno(1). More precisely, we achieve the following space-time tradeoffs:n1+o(1)space and log2+o(1)nquery time,nlog2+o(1)nspace andno(1)query time,n4/3+o(1)space and log1+o(1)nquery time.We reduce a distance query to a variety ofpoint locationproblems in additively weightedVoronoi diagramsand develop new algorithms for the point location problem itself using several partially persistent dynamic tree data structures.
登录
查看更多内容
DOI：
10.1007/3-540-48224-5_12
发表时间：
2001
期刊：
The American journal of physiology
影响因子：
--
作者：
G. Brodal;Rolf Fagerberg;Christian N. S. Pedersen;Anna Pagh
通讯作者：
Anna Pagh
O(n log log n) 时间内有向平面图的最小割
DOI：
10.1137/1.9781611975031.32
发表时间：
2015
期刊：
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing
影响因子：
--
作者：
S. Mozes;Kirill Nikolaev;Yahav Nussbaum;Oren Weimann
通讯作者：
Oren Weimann
平面图的最佳近似距离预言机
DOI：
10.1109/focs52979.2021.00044
发表时间：
2022
期刊：
2021 IEEE 62nd Annual Symposium on Foundations of Computer Science
影响因子：
--
作者：
Le, Hung;Wulff-Nilsen, Christian
通讯作者：
Wulff-Nilsen, Christian
一种新的质心分解线性时间算法
DOI：
10.1007/978-3-030-32686-9_20
发表时间：
2019
期刊：
The American journal of physiology
影响因子：
--
作者：
D. D. Giustina;N. Prezza;Rossano Venturini
通讯作者：
Rossano Venturini
具有改进边界的近似距离预言机
DOI：
--
发表时间：
2015
期刊：
Symposium on the Theory of Computing
影响因子：
--
作者：
S. Chechik
通讯作者：
S. Chechik