Higherorder Voronoi diagrams of polygonal objects
130 p
Thèse de doctorat: Università della Svizzera italiana, 2014
English
Higherorder Voronoi diagrams are fundamental geometric structures which encode the knearest neighbor information. Thus, they aid in computations that require proximity information beyond the nearest neighbor. They are related to various favorite structures in computational geometry and are a fascinating combinatorial problem to study. While higherorder Voronoi diagrams of points have been studied a lot, they have not been considered for other types of sites. Points lack dimensionality which makes them unable to represent various reallife instances. Points are the simplest kind of geometric object and therefore higher order Voronoi diagrams of points can be considered as the corner case of all higherorder Voronoi diagrams. The goal of this dissertation is to move away from the corner and bring the higherorder Voronoi diagram to more general geometric instances. We focus on certain polygonal objects as they provide flexibility and are able to represent reallife instances. Before this dissertation, higherorder Voronoi diagrams of polygonal objects had been studied only for the nearest neighbor and farthest Voronoi diagrams. In this dissertation we investigate structural and combinatorial properties and discover that the dimensionality of geometric objects manifests itself in numerous ways which do not exist in the case of points. We prove that the structural complexity of the orderk Voronoi diagram of noncrossing line segments is O(k(nk)), as in the case of points. We study disjoint line segments, intersecting line segments, line segments forming a planar straightline graph and extend the results to the Lp metric, 1<=p<=infty. We also establish the connection between two mathematical abstractions: abstract Voronoi diagrams and the ClarksonShor framework. We design several construction algorithms that cover the case of nonpoint sites. While computational geometry provides several approaches to study the structural complexity that give tight realizable bounds, developing an effective construction algorithm is still a challenging problem even for points. Most of the construction algorithms are designed to work with points as they utilize their simplicity and relations with datastructures that work specifically for points. We extend the iterative and the sweepline approaches that are quite efficient in constructing all orderi Voronoi diagrams, for i<=k and we also give three randomized construction algorithms for abstract higherorder Voronoi diagrams that deal specifically with the construction of the orderk Voronoi diagrams.

Language


Classification

Computer science

License

License undefined

Identifiers


Persistent URL

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