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.