Circle Expansion and abstract Voronoi diagrams

Voronoi图是非常重要的结构；它们在计算机科学和许多其他科学中都有应用。DACH项目VORONOI++旨在推广VORONOI图的概念，使更精确的现实世界模型成为可能。DACH项目的德语部分voroni++有以下目标。1)基于广义圆展开的Voronoi图分析。Voronoi图是由一组有限的点展开的圆产生的。每个点都属于该站点的Voronoi区域，圆圈首先到达它。第一次，我们想要研究如果膨胀速度随时间变化不恒定，并且取决于地点，会产生什么图表。这种方法包含了对标准Voronoi图的已知概化，并添加了可变速度作为一个新组件。初步结果表明，Voronoi区域可能会断开连接。我们想找出平分线的形状和Voronoi图的结构复杂性如何依赖于单个速度函数。2)抽象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.