Spacial Decompositions and Graphs

许多理论和实际的几何问题导致空间分解作为其分析或解决方案的一部分：Voronoi图及其对偶分解，Delaunay镶嵌只是最经典和最基本的例子。底层的“空间”可以是我们生活的欧几里得环境空间，或者是一些更抽象的参数空间，例如机器人的配置空间。一方面，关于经典的Voronoi图有许多困难的问题仍然是开放的（例如移动点的Voronoi图的复杂性）。另一方面，最近出现了许多可以被认为是Voronoi图的变化的空间分解，例如由一些收敛过程定义的分解，例如牛顿寻根法，或者与模式匹配问题有关的分解。对于这些新的结构，甚至一些基本的问题（如唯一性，细胞的基本结构）还没有被研究。四个主要的结构将被调查：（一）Voronoi图，（二）Skeleton结构，（三）三角形的变体，（四）邻近图。

Many theoretical and practical geometric problems lead to decompositions of space as part of their analysis or as part of their solution: The Voronoi diagram and its dual decomposition, the Delaunay tessellation is just the most classical and fundamental example. The underlying "space" can be the Euclidean ambient space that we live in, or some more abstract parameter space or for example the configuration space of a robot. On the one hand, there are many hard questions about the classical Voronoi diagrams that remain open (such as complexity of Voronoi diagrams of moving points). On the other hand, many spatial decompositions that can be considered as variations of Voronoi diagrams have recently emerged, for example decompositions defined by some converging process such as Newton's method for finding roots, or decompositions that are related to pattern matching problems. For these new structures, even some basic questions (like uniqueness, the basic structure of cells) have not been investigated. Four main structures will be investigated: (i) Voronoi diagrams, (ii) Skeletal structures, (iii) Variants of triangulations, and (iv) Proximity graphs.