The Taub Faculty of Computer Science Events and Talks

Given a set of points (sites) in the plane, a Voronoi diagram is a partitioning of the plane into regions such that each region contains one site and all points closer to this site than to any other site. Voronoi diagrams have practical and theoretical applications in a large number of fields. In this talk, I will overview the exciting new uses of Voronoi diagrams for planar graph algorithms. In particular, I will describe an efficient construction of Voronoi diagrams for planar graphs with two applications: computing the diameter in O(n^{5/3}) time, and computing exact distance oracles with O(n^{3/2}) space and O(log n) query time.