Title: Abstract Voronoi-like Graphs and Applications

Speaker: Evanthia Papadopoulou, Università della Svizzera italiana

Date and time: 6pm (New York time), Tuesday, May 9, 2023

Place: WWH1314 (room 1314 Warren Weaver Hall, 251 Mercer Street)

...and on Zoom, details on the seminar mailing list

Differences between classical Voronoi diagrams of points in the plane, versus Voronoi diagrams of segments, disks, polygons, or clusters of points, may sometimes get overlooked. As a result some basic questions concerning the latter diagrams remain open. In this talk I will discuss Voronoi-like graphs as a tool to address such problems.

A Voronoi-like graph is a relaxed Voronoi structure, defined as a graph on the arrangement of a planar bisector system (in the sense of abstract Voronoi diagrams) whose vertices are locally Voronoi. A vertex $v$ is called locally Voronoi, if $v$ and its incident edges appear in the Voronoi diagram of three sites. For points in the Euclidean plane, where the bisector system forms a line arrangement, any Voronoi-like graph is the Voronoi diagram of the involved sites. But how about bisector systems, which are not lines (nor pseudolines), such as those related to line-segments, disks, or abstract Voronoi diagrams? I will consider this question in this talk, and give simple expected linear-time algorithms to compute Voronoi (and Voronoi-like) trees and forests. Examples include updating an abstract Voronoi diagram, after deletion of one site, in linear expected time, updating a constraint Delaunay triangulation after inserting a new segment constraint, and others.

Some parts of this talk is joint work with Kolja Junginger.