2020/07/16 by Yaowei Long, Seth Pettie, Long, Yaowei +1
Computer Science · #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Data Management and Algorithms #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.DS
paper · pdf · doi:10.48550/arxiv.2007.08585
35 pages, 12 figures
arxiv created 2020/07/16 · openalex publication_date 2020/07/16 · arxiv updated 2020/07/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In a recent breakthrough, Charalampopoulos, Gawrychowski, Mozes, and Weimann (STOC 2019) showed that exact distance queries on planar graphs could be answered in no(1) time by a data structure occupying n1+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) = no(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 n1+o(1) space and log2+o(1)n query time, or nlog2+o(1)n space and no(1) query time. All previous oracles with O(1) query time occupy space n1+Ω(1), and all previous oracles with space O(n) answer queries in nΩ(1) time.