Skip to content (access key 's')
Logo of Technion
Logo of CS Department

The Taub Faculty of Computer Science Events and Talks

Theory Seminar: Voronoi Diagrams for Planar Graphs
event speaker icon
Oren Weimann (Haifa University)
event date icon
Wednesday, 11.04.2018, 12:30
event location icon
Taub 201
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.