Problems on planar voronoi diagrams
PhD: Università della Svizzera italiana
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 minmax 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 floodlightswedges. 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 wellknown deterministic lineartime 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


Classification

Computer science

License

License undefined

Open access status

green

Identifiers


Persistent URL

https://susi.usi.ch/usi/documents/320920