Problems on Planar Voronoi Diagrams

You are cordially invited to attend the PhD Dissertation Defence of Ioannis Mantas on Wednesday 12 January 2022 at 10:30 in room D1.13 or on MS Teams.

Abstract:
Computational Geometry is a field in Computer Science that studies algorithmic problems which can be expressed in terms of Geometry. A geometric structure that has attracted the interest of researchers over the last centuries is the Voronoi diagram. It is a powerful geometric object which has diverse applications on problems where proximity information is required. Given a set of sites, their Voronoi diagram is the subdivision of the space into regions, such that all points in a region have the same nearest site. Many generalizations of this simple concept have been considered, including generalized sites, spaces and distance functions. In this dissertation we study three problems related to generalized planar Voronoi diagrams. The first topic is related to color Voronoi diagrams, where each site is a cluster of points and the distance between a point and a cluster is the minimum Euclidean distance. Color Voronoi diagrams are motivated by facility location problems and sampling based approximation schemes for Voronoi diagrams. We focus on the farthest color Voronoi diagram, which is a min-max type of Voronoi diagram. We present combinatorial properties, conditions for the diagram to have linear complexity, and efficient construction algorithms. Secondly, we study the rotating rays Voronoi diagram, a Voronoi structure where the input sites are rays and the distance between a point and a ray is an oriented angular distance. We demonstrate how such a diagram finds applications in various floodlight illumination problems; coverage problems where a domain has to be covered by floodlights-wedges. Motivated by these illumination problems, we study the rotating rays Voronoi diagram in various domains of interest, as for example the plane, polygons, and curves. For all the domains considered we present combinatorial and algorithmic results. Finally, we consider a well-known deterministic linear-time algorithmic scheme for Voronoi diagrams. We generalize a combinatorial result on selecting leaves in embedded binary trees that the scheme requires, aiming to make this algorithmic technique applicable to larger classes of planar Voronoi diagrams.

Dissertation Committee:
- Prof. Evanthia Papadopoulou, Università della Svizzera italiana, Switzerland (Research Advisor)
- Prof. Piotr Krzysztof Didyk, Università della Svizzera italiana, Switzerland (Internal Member)
- Prof. Luca Maria Gambardella, Università della Svizzera italiana, Switzerland (Internal Member)
- Prof. Ioannis Emiris, University of Athens, Greece (External Member)
- Prof. Rodrigo Silveira, Universitat Politècnica de Catalunya, Spain (External Member)