Vi presenterar ett O(n 1.5 )-utrymme avstånd oracle för riktade planar grafer som svarar på avstånd frågor i O(log n) tid. Vårt orakel både avsevärt förenklar och avsevärt förbättrar den senaste oraklet av Cohen-Addad, Dahlgaard och Wulff-Nilsen [FOCS 2017], som använder O(n 5/3 )-utrymme och svarar på frågor i O(log n) tid. Vi uppnår detta genom att utforma en elegant och effektiv punkt platsdatastruktur för Voronoi diagram på plana grafer. Vi visar också en smidig avvägning mellan utrymme och frågetid. För alla S  till [n, n 2 ], visar vi en orakel av storlek S som svarar på frågor i Õ(max\1, n 1.5 /S}) tid. Denna nya kompromiss är för närvarande den bästa (upp till polylogaritmiska faktorer) för hela sortimentet av S och förbättrar genom polynomiska faktorer över alla tidigare kända kompromisser för intervallet S  på [n, n 5/3 ].
Den för närvarande mest kända kompromissen är en orakel av storlek Õ(n 3/2 /q), som besvarar frågor i tid Õ(q) för varje q  på [1, n 1/2 ] REF.
Better Tradeoffs for Exact Distance Oracles in Planar Graphs
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}