Baruch Discrete Math Group

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.