用于计算支配点的分而治之算法？

Question

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

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

现在,我有以下算法:

• 绘制一条垂直线,将点集点分为P _左和_右两个相等的子集.作为基础案例,如果只剩下两点,我可以直接比较它们.

• 递归计算P _left和P _right中支配对的数量

• 一些征服步骤？

问题是我无法看到"征服"步骤应该在这里.我想计算从P _左边到P _右边有多少支配对,但我不知道如何在不比较两个部分中的所有点的情况下这样做,这需要时间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)

根据主定理,这解决了O(n log ² n).

但是,你可以加快速度.假设在你开始划分amd征服步骤之前,你用y坐标预先分配点,做一次O(n log n)工作.使用类似于最接近的点对的技巧问题,然后可以在每个大小为n的子问题(参见本页底部的讨论)中以O(n)时间对每一半中的点进行排序以获得详细信息.这会将重复发生变为

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

根据需要,它解决了O(n log n).

希望这可以帮助!