University of Ljubljana & Institute of Mathematics, Physics and Mechanics, Ljubljana
Three Open Problems
I would like to share with you three open problems in Computational Geometry:
- Expected volume of the stochastic bounding box;
- Maximum matching in unit disk graphs or unit square graphs;
- Barrier resilience
For each of these problems, there are interesting results and I will discuss some of the ideas that have been used, but the main question remains open.
Universidad de Sevilla
Graph theory meets geometry
Geometric graph theory involves considering the realization of a graph in Euclidean space and studying its metric properties. This area has been extensively researched, with a vast literature available. However, there are certain functional differences between geometric graph theory and traditional graph theory, and studying these functional differences has been a focus of recent research. By considering the ways in which geometric graph theory differs from traditional graph theory, we can better understand how to modify geometric graphs in order to improve those functionals.
Joint work with several people, mainly D. Garijo and R. Silveira.
Università della Svizzera italiana
Abstract Voronoi-like Graphs and Applications
Differences between classical Voronoi diagrams of points, versus Voronoi diagrams of segments, disks, polygons, or clusters of points in the plane, tend sometimes to be overlooked. As a result some basic questions concerning the latter diagrams may remain open or non-optimally solved. In this talk, I will discuss Voronoi-like graphs as a tool towards resolving such differences.
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, 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.
Some parts of this talk are joint work with Kolja Junginger.
