Personal tools
You are here: Home CG seminar 2023 Voronoi-Like Graphs – Towards Simple Linear Time Algorithms for Voronoi Trees and Forests
« January 2023 »
January
SuMoTuWeThFrSa
1234567
891011121314
15161718192021
22232425262728
293031
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)

underline

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 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