Back
2022INF003
Doctoral thesis

Problems on planar voronoi diagrams

  • 2022

PhD: Università della Svizzera italiana

Computational geometry
Voronoi diagram
Farthest color voronoi diagram
Cluster voronoi diagram
Minmax voronoi diagram
Rotating rays voronoi diagram
Oriented angular distance
Floodlight illumination
Linear time construction algorithms
English Computational Geometry is the field of 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.
Collections
Language
  • English
Classification
Computer science and technology
License
License undefined
Open access status
green
Identifiers
Persistent URL
https://n2t.net/ark:/12658/srd1320920
Statistics
Document views: 40 File downloads:
  • 2022INF003.pdf: 129