Алгоритмы для динамических диаграмм Вороного

Computational geometry studies computations on discrete geometric objects such as arrange- ments, diagrams, foldings and drawings. In particular one of its main interests is to design algorithms to construct such objects and data structures that store them efficiently.
The most crucial and defining concept applied in all those constructions is distance: whatever is studied, there is always some underlying metric that describes the object in question and defines its properties. It can be just the Euclidean metric, or some polyhedral metric, or any other metric that corresponds to a surface or a folding of a polygon.
In this thesis, we consider two different types of a distance metric. The Euclidean metric in R2 gives rise to the ordinary Voronoi diagrams, and we develop an algorithm that allows for fast update of a Voronoi diagram that is stored explicitly. We also consider polyhedral metrics of the spaces induced by gluing congruent squares edge to edge, and we propose a way to classify all such spaces in time polynomial in .
Even though there are many well-known algorithms that construct the Voronoi diagram for a given family of sites [9], the problem of making a Voronoi diagram dynamic, i. e. implementing changes to it when a new point site is inserted, has only drawn attention in the implicit case: maintaining implicit Voronoi diagram can be done in very little time [11, 12, 20]. Maintaining a Voronoi diagram explicitly has not yet been considered.
The worst one can expect is that when a new site is inserted, the number of updates in a Voronoi diagram (i. e. vertices and edges that change) is linear. This can happen for every insertion if we consider an embedded diagram and store the coordinates of all the vertices.
The situation improves if we consider the graph of the Voronoi diagram that is subject to com- binatorial changes: no coordinates matter, it is just deletion or addition of edges that is performed. In Allen et al. [2] it was proved that when a new site is inserted to a Voronoi diagram, only (√ ) combinatorial changes happen to the graph of the diagram. This opened a possibility to find a sublinear algorithm that finds and implements combinatorial changes in an explicitly stored graph of the Voronoi diagram.
In this thesis we present the first algorithm sublinear in (which is the number of sites) that does exactly that. The algorithm has running time of ̃( 3/4), which still does not achieve the (√ ) bound on the number of changes, that is why the quest for a better algorithm is still open.
One can try to employ the well-known «divide and conquer» strategy to find such an algorithm: divide all the sites into two halves by a line and update only the half of the diagram that receives the new site. We show that adding a line as a site to the diagram still allows for a (√ ) upper bound on the number of combinatorial changes per insertion. This means that, theoretically, «divide and conquer» is a desirable approach.
Another type of metrics and distances that can be often seen in computational geometry is polyhedral metrics and geodesic distances. A question concerning them that has been standing for a long time already is the Alexandrov’s problem of finding a convex polyhedron corresponding to a given polyhedral metric. There is almost no hope of solving this problem exactly for an arbitrary polyhedral metric, that is why several special cases are considered in literature [6, 8, 15, 16, 17].
A result we achieved in this thesis is a significant advance for an important special case: we present a polynomial-time algorithm to classify all the edge-to-edge gluing of at most squares. It is a development of my bachelor’s thesis making use of its results and an answer to a natural open question.
3
Our results open new directions for subsequent studies: it rises new questions that can be asked — like finding more efficient algorithms or enumerating gluings of other polygons, and suggests new possible methods that can be used to answer them.
This thesis is based in part on published articles and given talks: the part concerning sublinear explicit incremental planar Voronoi diagrams has been presented at JCDCG3 [4] and published in Journal for Information Processing [5], and the part concerning gluings of squares has been accepted for SoCG Young Researchers Forum 2021 [22]. The latter is a development of the bachelor’s thesis of the same author [26].
The rest of this section contains the main definitions and results that will be necessary for the main body of this thesis.