一个用于计算支配点的分治算法？

Question

假设坐标为(x1,y1)的一个点支配另一个点(x2，y2)，如果x1≤x2且y1≤y2，则称该点支配另一个点。

我有一组点(x1,y1)，....(xn,yn)，想要找出总共有多少支配对。使用暴力方法可以将所有点两两比较，但这需要时间O(n^2)。相反，我想使用分治法在O(nlogn)的时间内解决这个问题。

目前，我有以下算法：

- 绘制垂直线将点集分成两个等分的子集Pleft和Pright。如果只剩下两个点，则可以直接比较。 - 递归计算Pleft和Pright中支配对的数量 - 一些征服步骤？

问题在于我不知道这里的“征服”步骤应该是什么。我想计算从Pleft到Pright跨越的支配对的数量，但我不知道如何做到这一点，而不必比较两个部分中的所有点，这将需要O(n^2)的时间。

有人能给我关于如何进行征服步骤的提示吗？

- ERJAN

Answer 1

假设您将点分别按其y坐标的升序排序。现在，查看两个部分中最低的y值点。如果左侧的最低点具有比右侧最低点更低的y值，则该点被右侧所有点支配。否则，右侧底部点不会支配左侧任何点。

在任一情况下，您都可以从两个部分中的一个中删除一个点，并使用剩余的排序列表重复此过程。每个点都需要O(1)的工作量，因此如果总共有n个点，则这需要O(n)的工作量（在排序后）来计算两个部分之间的支配对数。如果您以前见过它，这类似于计算数组中逆置数量的算法。

考虑到排序点所需的时间（O(n log n)），这个征服步骤需要O(n log n)的时间，给出递归式

T(n) = 2T(n / 2) + O(n log n)

根据主定理，这解决为O(n log^2 n)。

然而，您可以加快此过程。假设在开始分治步骤之前，通过其y坐标对点进行预排序，执行一次O(n log n)的工作。使用类似于最接近点对问题的技巧，您可以在每个大小为n的子问题上以O(n)的时间获取每半部分中的点（有关详细信息，请参见此页面底部的讨论）。这将更改递归为

T(n) = 2T(n / 2) + O(n)

按要求解决为O(n log n)。

希望这可以帮到您！

- templatetypedef

---

好的，但是我对这个有些困惑：“通过右侧所有点”。这是否意味着左侧最低的y被右侧的所有点支配，包括其自身左侧部分中的点？例如：左侧y = {1,3,4,5,5}；右侧y = {5,8,9,10,12}，所以1 < 5 => 1小于右侧y中的所有点？但是左侧y中的剩余点{3,4,5,5}怎么样？这有点不清楚你指的“右侧”是哪一个。 - ERJAN

另外，我应该进行递归调用，直到每个子集中只剩下2个点吗？还是只需将整个列表分成两半，然后仅比较y坐标？ - ERJAN

查找上面的情节 - 我正在使用这个例子。 - ERJAN

@ERJAN- 这样考虑一下。假设您通过绘制一条垂直线将点分成“左”和“右”两半。递归计算两个半部分中支配点的数量。现在，要考虑的仅是支配点对，即一个点在左半部分，另一个点在右半部分。右边的任何点都已经具有比左边任何点更大的x坐标，因此仅剩下的考虑是右边的哪些点具有高于左边点的y值。我建议的算法提供了一种高效计算的方法... - templatetypedef

@ERJAN- ...穿过分裂的支配点数量。这样清楚了吗？ - templatetypedef

Answer 2

在这种情况下，你需要将元素分成子集，时间复杂度为O(n^2)。我的方法不同，具体如下：

1. 按照X坐标对点进行排序... O(n.log(n))
2. 现在检查Y坐标
   • 但只检查X坐标更大的点（如果你按升序排序，则是更大的索引）
3. 因此，现在时间复杂度为O(n.log(n)+(n.n/2))

你也可以通过分别进行X和Y测试并在之后组合结果来进一步加快速度，这将导致O(n + 3.n.log(n))的时间复杂度。

1. 给你的点添加索引属性
   • 其中 index = 0xYYYYXXXXh 是无符号整数类型
   • YYYY 是点在 Y 排序数组中的索引
   • XXXX 是点在 X 排序数组中的索引
   • 如果你有超过 2^16 个点，则使用大于 32 位的数据类型。
2. 按升序对点进行排序并设置其索引的 XXXX 部分 O1(n.log(n))
3. 按升序对点进行排序并设置其索引的 YYYY 部分 O2(n.log(n))
4. 按升序对点进行排序 O3(n.log(n))
5. 现在，如果 (i < j)，则点 i 支配任何点 j
   • 但是，如果您需要为任何点实际创建所有成对组合
   • 那将需要 O4(n.n/2) 的时间，因此这种方法不会节省任何时间
   • 如果您只需要任何点的一个成对组合，则简单循环就足够了 O4(n-1)
   • 因此，在这种情况下，O(n-1+3.n.log(n)) -> ~O(n+3.n.log(n))

希望这有所帮助，如果您坚持使用细分方法，那么我没有更好的解决方案。PS. 对于这个问题，您不需要任何额外的递归，只需要进行3次排序，并且每个点只需要一个uint，因此内存要求并不大，甚至应该比一般的细分递归调用更快。

- Spektre

Answer 3

该算法的时间复杂度为 O(N*log(N))，其中 N 是点列表的大小，并且它使用 O(1) 的额外空间。

执行以下步骤：

1. 按 y 坐标（升序）对点列表进行排序，如果出现并列，则按 x 坐标（升序）排序。
2. 倒序遍历已排序的列表以计算支配点数：如果当前 x 坐标 >= 迄今为止遇到的最大 x 坐标值，则增加结果并更新最大值。

这个算法之所以有效，是因为你可以确定，如果所有具有更大 y 坐标的点都比当前点的 x 坐标小，那么你就找到了一个支配点。排序步骤使其真正高效。

以下是 Python 代码：

def my_cmp(p1, p2):
    delta_y = p1[1] - p2[1]
    if delta_y != 0:
        return delta_y
    return p1[0] - p2[0]

def count_dom_points(points):
    points.sort(cmp = my_cmp)
    maxi = float('-inf')
    count = 0
    for x, y in reversed(points):
        if x >= maxi:
        count += 1
        maxi = x

    return count

- LorenzoS