# 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.