Voronoilike diagrams : towards lineartime algorithms for treelike abstract Voronoi diagrams
112 p
Thèse de doctorat: Università della Svizzera italiana, 2020
English
Computational Geometry is a subfield of Algorithm Design and Analysis with a focus on the design and analysis of algorithms related to discrete geometric objects. The Voronoi diagram is one of the most important structures in Computational Geometry providing proximity information, which is applicable to many different fields of science. For a given set of points in the plane – called sites – the classic Voronoi diagram subdivides the plane into regions, such that all points within one region have the same nearest site. Abstract Voronoi diagrams provide a unifying model for various concrete Voronoi diagrams for different sites and different metrics. For example the sites can be disjoint line segments or nonenclosing circles, disjoint convex polygons of constant size and the metrics include all Lp metrics, the Karlsruhe metric and other convex distance measures. In the abstract framework the diagram is not defined via the sites and the distances, but from a bisecting curve system satisfying certain properties. Updating the classic Voronoi diagram of point sites, after deletion of one site, can be done in linear time as it is well known since 1989. However, this problem has remained open since then for generalized sites other than points and for abstract Voronoi diagrams. In this dissertation we present a simple, expected lineartime algorithm to update an abstract Voronoi diagram after deletion of one site. To this aim we introduce the concept of a Voronoilike diagram, a relaxed version of a Voronoi construct that has a structure similar to an abstract Voronoi diagram, without however being one. In our algorithm Voronoilike diagrams serve as intermediate structures, which are considerably simpler to compute. We formalize the concept of a Voronoilike diagram and prove that it is welldefined and robust under an insertion operation, thus, enabling its use in incremental constructions. Further, we show that our randomized algorithm can be used to compute the order(k+1) subdivision within the face of an orderk abstract Voronoi region in expected time linear in the complexity of the region’s boundary. Moreover, our randomized algorithm can be adapted to compute the farthest abstract Voronoi diagram in expected lineartime, after the sequence of its faces at infinity is known. Finally, we have investigated the possibility to apply Voronoilike diagrams also to a deterministic algorithmic framework for possible use in deriving deterministic versions of the above mentioned randomized algorithms. We formulate open problems, the solution of which will make progress towards this goal.

Language


Classification

Computer science

License

License undefined

Identifiers


Persistent URL

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