data-structures - 财富算法 - 海滩线数据结构

Question

我必须实现 Fortunes algorithm用于构建 Voronoi 图。

该算法的重要部分是称为“海滩线数据结构”的数据结构。

它是一个二叉平衡树，类似于 AVL，但不同之处在于数据仅存储在叶子上(还有其他差异，但对于问题并不重要)。

我不确定如何实现它。显然，“按原样”使用 AVL 是行不通的，因为在平衡 AVL 时，树叶节点可以成为内部节点，反之亦然。

我还尝试在 wikipedia 上查看其他一些已知的数据结构，但没有一个适合需求。
我已经看到一些使用链表执行此操作的实现，但这并不好，因为搜索链表是 O(n)，并且它需要 O(log n) 才能使算法有效。

Answer 1

叶子确实存储(单个)点，而事件结构(“海滩线树”)的内部节点存储点的有序元组，其抛物线/弧彼此相邻。如果抛物线那点霸 形式位于由 形成的抛物线的左侧铅 (并且这两条抛物线相交)，内部节点存储有序元组 (Pa, Pb) .

Obviously using AVL "as is" will not work because when balancing AVL tree leaf node can become inner node and vice versa.

如果您担心在 AVL 树中存储不同类型的对象，一个简单的方案是将叶子也存储为元组。所以不要存点 Pj 作为叶子，但存储元组 (Pj, Pj) 反而。如 Pj 当一片叶子从事件树(海滩线)中消失时，它的父节点是 (Pi, Pj) ，只需将父级更改为 (Pj, Pj) ，当然它的父级也需要从 改变(Pj，P？)至 (Pi，P？)等等。就像使用常规 AVL 树一样:您沿着树向上走并修改需要更改和/或重新平衡的内部节点。

请注意，算法的良好实现不能轻易写在 SO 答案中(至少，不是我写的!)。有关整个算法的正确解释，包括它使用的数据结构的描述，请参阅 Computational geometry: algorithms and applications by Mark de Berg et al. .第 7 章专门讨论 Voronoi 图。