Algorithms Seminar

Voronoi diagrams and diameter for planar graphs

Speaker:Micha Sharir
Date: Wednesday, November 15, 2017
Time: 3:00pm - 4:00pm
Location: D344 LSRC, Duke


In this talk I will survey some older and newer results concerning the computation of distances in planar graphs, and then go into some of the details of efficiently constructing weighted Voronoi diagrams for planar graphs, and one of their main applications: Computing the diameter of a directed, weighted planar graph in (close to) deterministic O(n^{5/3}) time. This follows the footprints of Cabello's recent breakthrough, but significantly improves his bound and simplifies the approach. Based on joint work with Pawel Gawrychowski, Haim Kaplan, Shay Mozes, and Oren Weimann.


Micha Sharir received his Ph.D. in Mathematics from Tel Aviv University in 1976, and then switched to Computer Science, doing his postdoctoral studies at the Courant Institute of New York University. He returned to Tel Aviv University in 1980, and has been there, at the School of Computer Science, ever since. He is also a visiting research professor at the Courant Institute, where he has been the deputy head of the Robotics Lab (1985-89). He has served as the head of the Computer Science Department (twice) and as the head of the School of Mathematics (1997-99). He is one of the co-founders of the Minerva Center for Geometry at Tel Aviv University. His research interests are in computational and combinatorial geometry and their applications. He has pioneered (with Jack Schwartz) the study of algorithmic motion planning in robotics during the early 1980s, and has been involved in many fundamental research studies that have helped to shape the fields of computational and combinatorial geometry. Among his major achievements, in addition to his earlier work on robotics, are the study of Davenport-Schinzel sequences and their numerous geometric applications, the study of geometric arrangements and their applications, efficient algorithms in geometric optimization (including the introduction and analysis of generalized linear programming), and the study of combinatorial problems involving point configurations. His work won him several prizes, including a Max-Planck research prize (1992, jointly with Emo Welzl), the Feher Prize (1999), the Mif'al Hapais' Landau Prize (2002), and the EMET Prize (2007). He is the incumbent of the Nizri Chair in computational geometry and robotics, a Fellow of the Association for Computing Machinery (since 1997), and has an honorary doctorate degree from the University of Utrecht (1996). He has supervised more than 25 Ph.D. students, many of which are now at various stages of an academic career, in Israel and abroad.