This website uses third party cookies to improve your experience. If you continue browsing or close this notice, you will accept their use.

Geometric algorithms: Voronoi diagrams and graph morphing

4 November 2019 at 11:30 AM - 1:00 PM

Room 304a, Campus on Viale Romania, 32

Speaker: Elena Arseneva , St Petersburg State University


We will discuss two topics in the area of geometric algorithms: cluster Voronoi diagrams and graph morphing. The Voronoi diagram is a fundamental geometric structure that encodes proximity information. Given a set of geometric objects, called sites, their Voronoi diagram is a subdivision of the underlying space into regions according to their nearest neighbor (maximal regions, such that all points within one region have the same nearest site). This simple concept and its generalizations have numerous applications, both in practice and in theory. We will talk about the Hausdorff and the farthest-color Voronoi diagrams (and also learn how they can be used in playing the "Taboo" game).  Afterwards we will talk about morphing between different straight-line drawings of the same graph. At each step of the morphing procedure, every vertex moves along a line segment  with a uniform speed, and the task is to ensure that the edges which are straight line segments do not collide at any moment, while the number of steps stays small. It is known that if the underlying space is the Euclidean plane,  it is sufficient and sometimes necessary to take the number of steps linear in the size of our graph. Morphing graphs in three dimensions is a vastly unexplored direction. I will tell about first steps taken there (fast morphing between plane trees using 3D, a tight bound on morphing between 3D drawings of trees), and several open problems.