Seminars & Colloquia Calendar

Download as iCal file

DIMACS Theory of Computing Seminar

Planar Distance Oracles

Seth Pettie (U Mich)

Location:  https://theory.cs.rutgers.edu/theory_seminar
Date & time: Wednesday, 28 October 2020 at 11:00AM - 12:00PM

Abstract: We consider the problem of preprocessing a weighted planar graph in order to answer exact distance and shortest path queries. As in the recent algorithms of Cohen-Addad et al. (2017), Gawrychowski et al. (2018), and Charalampopoulos et al. (2019), our algorithm is based on solving the point-location problem in weighted planar Voronoi diagrams.

We give a new, efficient method to solve point location using persistent data structures, which leads to a new time-space tradeoff for the problem. At the extremes of this tradeoff, the data structure: * occupies \(n^{1+o(1)}\) space and answers distance queries in \(log^{2+o(1)} n\) time, or

* occupies \(nlog^{2+o(1)} n\) space and answers distance queries in \(n^{o(1)}\) time.

Joint work with Yaowei Long, to appear in SODA 2021. arXiv:2007.08585.

Mailing list

Special Note to All Travelers

Directions: map and driving directions. If you need information on public transportation, you may want to check the New Jersey Transit page.

Unfortunately, cancellations do occur from time to time. Feel free to call our department: 848-445-6969 before embarking on your journey. Thank you.