二进制空间分区算法的预期运行时间

Question

在Mark de Berg的《计算几何：算法与应用》中，您可以找到以下二进制空间分区算法：

BSP(Finite set of finite non-intersecting line segments S)
{
    if (n > 1)
    {
        Use the extension of the first segment in S as the splitting line L
        Let S+ and S- be the set of fragments above and below L, respectively
        Create a tree T with left subtree = BSP(S-) and right subtree BSP(S+)
        Store all segments which overlap with L in T
    }
    else
        Create a tree T and store S in T
    return T
}

如果分割线 L 将段切成两半，则会生成片段。你可能想看看我的另一个问题，我举了一个这个过程的例子。

我们可以证明，如果段是随机洗牌的（使得这些段的每个可能的排列都有相等的出现概率），并且n表示段的数量，则BSP生成的片段的预期数量最多是n + 2n log(n)。

我们如何绑定预期的递归调用数量？

在de Berg的书中，作者指出，递归调用的预期数量受预期生成的片段数量的限制。为什么？

---

显然，一条分裂线L最多可以产生n - 1个新的碎片。在最坏的情况下，所有这些新碎片都在L的一侧。在这种情况下，S+和S-中的每一个都将包含n - 1元素。因此，我们将有两个递归调用，输入大小为 n - 1 。这导致递归运行时间为 T(n) = n - 1 + 2 * T(n - 1) 。[n - 1原因是我们需要测试它们是否高于或低于L 的元素计数]。

我们可以展开递归，但我认为这将产生一个非常糟糕的估计。那么，我们需要怎么做呢？我们如何利用已知的预期生成的片段数量？

Answer 1

对

S 非空的 BSP 的调用与生成的片段一一对应。每次调用最多进行一次 S 为空的递归调用，这不会进行递归调用，因此调用总数受生成片段数的两倍限制。因此，这种说法是意料之中的。

Answer 2

"我们如何绑定预期的递归调用数量？"：你不能。算法说明说明，此预期数量受预期片段数的限制，您无法直接控制这些片段。

当段足够随机时，这个数字是 O（N Log（N）），这很好。但对于其他分布，它可能更高甚至更低。

此外，您还担心最坏的情况，其复杂性可能是灾难性的（如 O（N²））。

为了规避这一点，您可能应该开发启发式方法，以平衡拆分并且不会生成太多片段的方式执行行 L 的选择。但你不能完全避免最坏的情况，只是让它变得极不可能。

这种情况让人想起快速排序，它有 O（N Log（N）） 预期行为，但 O（N²） 最坏情况。后者通过使用"三的中位数"启发式来选择枢轴来驯服。

Answer 3

我们表明，每次输入算法主体时，都会消耗一个片段：

• 我们可以忽略S为空的情况，因为这可能会在算法中被"黑客入侵"，从而避免递归调用
• 如果 S 包含单个元素，则使用此元素（并且不会发生进一步的递归调用）
• 如果 S 包含多个元素，则至少使用S的第一个元素，因为它被选为拆分行l（并且不会发生进一步的递归调用）;事实上，与l重叠的所有元素都被消耗S（但同样，这在这里无关紧要，因为我们对最坏情况感兴趣）

因此，递归调用的数量受生成的片段的数量限制。由于期望生成的片段数是O(n ln n)，递归调用的预期数也是O(n ln n)。