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

diagrams of segments, circles, polygons, or clusters of points in the
plane, 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.