Personal tools
You are here: Home CG seminar Spring 2017 Voronoi diagrams, diameter and distance oracles for planar graphs
« November 2017 »
November
SuMoTuWeThFrSa
1234
567891011
12131415161718
19202122232425
2627282930
Log in


Forgot your password?
 

Voronoi diagrams, diameter and distance oracles for planar graphs

Wednesday, June 21st, 2017 16:10

Schreiber 309

underline

Voronoi diagrams, diameter and distance oracles for planar graphs

Shay Mozes, IDC

Abstract:

Computing distances in graphs is a fundamental and important problem. In this talk I will survey some older and newer results concerning the computation of distances in planar graphs. I then plan to go into some of the details of efficiently constructing weighted Voronoi diagrams for planar graphs. I will also discuss two applications: computing the diameter in O(n^{5/3}) time, and exact distance oracles with O(n^{3/2}) space and O(log n) query time.
 
Based on joint works with Pawel Gawrychowski, Haim Kaplan, Micha Sharir, and Oren Weimann. 
Document Actions