algorithm - 用于计算控制点的分而治之算法？

Question

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

我有一组点 (x1,y1) , ....(xn,yn) 并且我想找出支配对的总数。我可以通过比较所有点来使用蛮力来做到这一点，但这需要时间 O(n²)。相反，我想使用分而治之的方法及时解决这个问题 O(n log n)。

现在，我有以下算法:

• 绘制一条垂直线，将点集分为 P_left 和 P_right 两个相等的子集。作为基本情况，如果只剩下两个点，我可以直接比较它们。

• 递归计算P_left和P_right

  中的支配对数量

• 一些征服步骤？

问题是我在这里看不到“征服”步骤应该是什么。我想计算从 P_left 到 P_right 有多少个支配对，但如果不比较两者的所有点，我不知道该怎么做部分，这将花费时间 O(n²)。

谁能给我一些关于如何进行征服步骤的提示？

所以 y 坐标的两半是:{1,3,4,5,5} 和 {5,8,9,10,12}

我画了分割线。

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)

根据 Master Theorem 求解为 O(n log² n) .

但是，您可以加快速度。假设在开始分而治之步骤之前，您按 y 坐标对点进行预排序，完成一次 O(n log n) 工作。使用类似于最近点对问题的技巧，您可以在 O(n) 时间内对每个大小为 n 的子问题(请参阅 the discussion at this bottom of this page 了解详细信息)排序。这将重复更改为

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

根据需要求解为 O(n log n)。

希望这对您有所帮助!