# Voronoi-Like Graphs – Towards Simple Linear Time Algorithms for Voronoi Trees and Forests

### Wednesday, January 11th, 4:10pm Tel Aviv time (3:10pm CET, 9:10am NY time)

### Evanthia Papadopoulou, Università della Svizzera italiana

### Abstract:

Differences between classical Voronoi diagrams of points, versus Voronoi

diagrams of segments, circles, polygons, or clusters of points in theplane, are sometimes overlooked or underestimated. As a result some

basic questions concerning the latter diagrams may surprisingly remain

open to date. In this talk I will discuss Voronoi-like graphs as a tool

towards addressing such problems.

A Voronoi-like graph is a relaxed Voronoi structure, defined as a graph

on the arrangement of a given bisector system. In a Voronoi-like graph,

a vertex v and its incident edges, within a small neighborhood around v,

must appear in a Voronoi diagram of three sites. For points in the

Euclidean plane, where the bisector system forms a line arrangement, a

Voronoi-like graph always coincides with the Voronoi diagram of the

involved sites. How about bisector systems which are not lines (nor

pseudolines), such as those related to line-segments, or more generally,

to abstract Voronoi diagrams? I will answer this question in this talk

and give examples of simple expected linear-time algorithms to compute

Voronoi-like trees (or forests). Examples include updating an abstract

Voronoi diagram after deletion of one site, updating a constraint

Delaunay triangulation after inserting a new segment constraint, and

others. As a byproduct, I will also discuss a simple alternative to

backwards analysis applicable to order-dependent structures.

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