Personal tools
You are here: Home CG seminar 2023 Voronoi-Like Graphs – Towards Simple Linear Time Algorithms for Voronoi Trees and Forests
« January 2023 »
Log in

Forgot your password?

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


Differences between classical Voronoi diagrams of points, versus Voronoi
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.
Document Actions