Circle Expansion and abstract Voronoi diagrams

Voronoi图是非常重要的结构；它们在计算机科学和许多其他科学中都有应用。DACH项目Voronoi++旨在推广Voronoi图的概念，使更精确的真实世界模型成为可能。DACH项目Voronoi++的德国部分有以下目标：1)基于广义圆展开的Voronoi图的分析。Voronoi图是由有限站点集的圆扩展而来的。每个点都属于该地点的沃罗诺伊地区，该地区的圆圈最先到达它。第一次，我们想要研究如果扩展速度不随时间而恒定，并且依赖于站点，会产生什么图表。这种方法包括已知的按单个权重的标准Voronoi图的推广，并添加了可变速度作为新的组成部分。第一个结果表明，沃罗诺伊区很可能变得不相连。我们想找出产生的Voronoi图的平分线形状和结构复杂性是如何取决于各个速度函数的。2)抽象Voronoi图的推广和构造抽象Voronoi图的有效算法。抽象Voronoi图(AVDS)是申请人在1989年提出的一个统一的概念，以涵盖尽可能多的具体类型的Voronoi图。它们不是基于场地、圆或距离度量，而是基于具有某些简单组合属性的平分曲线。只要在具体情况下满足这些条件，AVD理论的结构结果和有效算法就可以直接应用到具体案例中；相当多的作者能够利用这一事实。到目前为止，平分线被认为是无界的，并生成连通的Voronoi区域。这些公理现在应该放宽，以涵盖1)中提到的图表，这些图表可能展示闭合的平分线曲线，以及在其他Voronoi++项目中研究的图表类型。3)交互式Java小程序。为了研究新型的Voronoi图，并进行实验，必须实现交互式Java小程序。在这里，我们可以建立在申请人的几何实验室中提供的几何基本体。稍后，这些小程序将提供给社区使用。

Voronoi diagrams are structures of fundamental importance; they have applications in computer science and in many other sciences. The DACH project VORONOI++ is aiming to generalize the concept of Voronoi diagrams to an extent that more precise models of the real world become possible. The german part of the DACH project VORONOI++ has the following goals.1) Analysis of Voronoi diagrams based on generalized circle expansion.Voronoi diagrams result from circles expanding from a finite set of sites. Each point belongs to the Voronoi region of that site whose circles reach it first. For the first time, we want to investigate what diagrams result if the expansion speeds are not constant over time, and depend on the sites. This approach includes known generalizations of standard Voronoi diagrams by individual weights, and adds variable speeds as a new component. First results indicate that Voronoi regions are likely to become disconnected. We would like to find out how the bisector shapes and the structural complexity of the resulting Voronoi diagrams depend on the individual speed functions. 2) Generalization of abstract Voronoi diagrams and efficient algorithms for constructing them.Abstract Voronoi diagrams (AVDs) were introduced by the applicant in 1989 as a unifying concept, to cover as many as possible concrete types of Voronoi diagrams. They are not based on sites, circles, or distance measures, but on bisecting curves that have certain simple combinatorial properties. Whenever these are fulfilled in a concrete situation, structure results and efficient algorithms from AVD theory can be directly applied to the concrete case; quite a few authors were able to make use of this fact. So far bisectors were supposed to be unbounded, and to generate connected Voronoi regions. These axioms shall now be relaxed in order to cover the diagrams mentioned in 1), which may exhibit closed bisector curves, as well as the diagram types studied in the other VORONOI++ projects. First results on disconnected regions are encouraging.3) Interactive Java applets.In order to study new types of Voronoi diagrams, and to perform experiments, interactive Java applets shall be implemented. Here we can build on geometric primitives available in the applicant's geometry lab. Later, these applets will be made available to the community.