Back
Texte intégral
Doctoral thesis

Voronoi-like diagrams : towards linear-time algorithms for tree-like abstract Voronoi diagrams

    25.06.2020

112 p

Thèse de doctorat: Università della Svizzera italiana, 2020

Abstract Voronoi diagram
Linear-time algorithm
Randomized incremental construction
Site-deletion
Higher-order Voronoi diagram
Farthest Voronoi diagram
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 non-enclosing 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 linear-time algorithm to update an abstract Voronoi diagram after deletion of one site. To this aim we introduce the concept of a Voronoi-like 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 Voronoi-like diagrams serve as intermediate structures, which are considerably simpler to compute. We formalize the concept of a Voronoi-like diagram and prove that it is well-defined 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 order-k 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 linear-time, after the sequence of its faces at infinity is known. Finally, we have investigated the possibility to apply Voronoi-like 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
  • English
Classification
Computer science and technology
License
License undefined
Identifiers
Persistent URL
https://n2t.net/ark:/12658/srd1319121
Statistics
Document views: 71 File downloads:
  • 2020INFO013.pdf: 160