论文标题
简单多边形中的动力学大地伏罗尼图
Kinetic Geodesic Voronoi Diagrams in a Simple Polygon
论文作者
论文摘要
我们研究了带有$ M $ Vertices的静态简单Polygon $ P $的$ N $ $ n $移动站点的$ n $ $ n $ s $ s $ n $ thine网站的voronoi图。我们确定了所有事件，其中Voronoi图的结构会改变，绑定此类事件的数量，然后开发动力学数据结构（KDS），该结构（KDS）随着站点移动而保持测量的Voronoi图。为此，我们首先分析一个由两个站点定义的单个分配器的频率，或一个由三个站点定义的单个Voronoi中心可以改变。对于这两种结构，我们都证明这种更改的数量最多为$ O（m^3）$，在最坏的情况下这很紧。此外，我们为这两种结构开发了紧凑，响应，局部和有效的动力学数据结构。我们的数据结构使用线性空间并处理最佳的最佳事件。我们的双配音器和Voronoi中心动力学数据结构以$ O（\ log^2 m）$时间处理每个事件。可以扩展两种结构，以有效地支持更新站点的移动。使用这些数据结构作为构建块，我们获得了一个紧凑的KD，以维护完整的大地测量Voronoi图。
We study the geodesic Voronoi diagram of a set $S$ of $n$ linearly moving sites inside a static simple polygon $P$ with $m$ vertices. We identify all events where the structure of the Voronoi diagram changes, bound the number of such events, and then develop a kinetic data structure (KDS) that maintains the geodesic Voronoi diagram as the sites move. To this end, we first analyze how often a single bisector, defined by two sites, or a single Voronoi center, defined by three sites, can change. For both these structures we prove that the number of such changes is at most $O(m^3)$, and that this is tight in the worst case. Moreover, we develop compact, responsive, local, and efficient kinetic data structures for both structures. Our data structures use linear space and process a worst-case optimal number of events. Our bisector and Voronoi center kinetic data structures handle each event in $O(\log^2 m)$ time. Both structures can be extended to efficiently support updating the movement of the sites as well. Using these data structures as building blocks we obtain a compact KDS for maintaining the full geodesic Voronoi diagram.
