递归如何在分裂和征服最大值集算法中工作？

Question

以下是Goodrich算法教科书中的伪代码算法，用于查找一组点中的主导2D点，称为查找最大值集：

Algorithm MaximaSet(S):

Input: A set,S,of n points in the plane

Output: The set, M, of maxima points in S 

if n ≤ 1

then return S  

Let p be the median point in S, by lexicographic (x,y)-coordinates 

Let L be the set of points lexicographically less than p in S 

Let G be the set of points lexicographically greater than or equal to p in S 

 M1 ←MaximaSet(L) 
 M2 ←MaximaSet(G) 

 Let q be the lexicographically smallest point in M2 

  for each point, r, in M1 do 

              if x(r) ≤ x(q) and y(r) ≤ y(q) 

              then Remove r from M1 

 return M1 ∪ M2

我的问题是在第10,11行的两个递归调用。我的理解是，在第10行第一次调用M1会将L侧分成另一个L和G组，然后将下一个L分成另一个L和G组，直到一组保持不变，下一行将运行并执行同样的事情是G方面的M2，但现在它如何与q进行比较？有人能帮助我追踪这个算法的征服部分吗？

特定

(1,4) (2,6), ( 3,1) (4,5) (5,7) (6,9) (7,2), (8,6) (9,3)

我知道最大值集是（6,9）（8,6）（9,3）但我仍然坚持使用THIS算法得到的确切结果。我通过蛮力解决了这个问题。这开始是一个硬件问题，我在技术上可以继续，因为我确实找到了答案，但我真的需要了解这一点，我已经尝试了2本教科书和谷歌，但我想我这次需要一个人。提前谢谢，因为这是我第一次上堆，请不要犹豫（请，请）给我任何更正我如何问我的问题或提出我的p代码

Answer 1

征服部分的想法是，你必须假设返回的集合M1和M2满足这个条件：

同一组中的任何一对点都可以共存

也就是说，集合中的任何一对点必须满足x1 < x2 && y1 > y2

在合并M1和M2之后，你应该返回一个满足这个条件的集合，最后我们获得的集合就是答案。

有一点需要注意的是，我认为合并时，x实际上不需要进行比较，因为M1中的所有点应该具有x <=而不是M2中的那些点

---

我们使用q，M2中的第一个点与M1中的所有点进行比较，因为

1. 如上所述，q不需要与M2中的其他元素进行比较
2. 在视觉上，q是x中最小的y和最大M2的点，正如所提到的，所有M1的x应该小于M2中的所有点，所以这里的主要点是q在y中有最大的M2，因此是最大的“潜力”到在M1覆盖（elminitate）点

结合1和2，该算法使用q来比较M1中的所有点以试图消除绝望的候选者，并将那些留下与M2结合起来形成满足上述条件的新集合。

---

让我们使用您的示例进行演示：

除以：（1,4）（2,6）（3,1）（4,5）（5,7）（6,9）（7,2）（8,6）（9,3）; L =（1,4）（2,6），（3,1）（4,5）（5,7）; R =（6,9）（7,2），（8,6）（9,3）

除以：（1,4）（2,6）（3,1）（4,5）（5,7）; L =（1,4）（2,6），（3,1）; R =（4,5）（5,7）

除以：（1,4）（2,6）（3,1）; L =（1,4）（2,6）; R =（3,1），返回{（3,1}）

除以：（1,4）（2,6）; L =（1,4）;返回{（1,4）}; R =（2,6）;返回{（2,6）}

除以：（4,5）（5,7）; L =（4,5）;返回{（4,5）}; R =（5,7）;返回{（5,7）}

征服：（1,4）（2,6）; M1 = {（1,4）}; M2 = {（2,6）} q =（2,6）; return merged set = {（2,6）}

征服：（1,4）（2,6）（3,1）; M1 = {（2,6）}; M2 = {（3,1）}; q =（3,1）; return merged set = {（2,6），（3,1）}

征服：（4,5）（5,7）; M1 = {（4,5）}; M2 = {（5,7）}; q =（5,7）; return merged set = {（5,7）}

征服：（1,4）（2,6）（3,1）（4,5）（5,7）; M1 = {（2,6），（3,1）}; M2 = {（5,7）}; q =（5,7）; return merged set = {（5,7）}

除以：（6,9）（7,2）（8,6）（9,3）; L =（6,9）（7,2）; R =（8,6）（9,3）

除以：（6,9）（7,2）; L =（6,9）;返回{（6,9}）; R =（7,2）;返回{（7,2）}

除以：（8,6）（9,3）; L =（8,6）;返回{（8,6）}; R =（9,3），返回{（9,3）}

征服：（6,9）（7,2）; M1 = {（6,9）}; M2 = {（7,2）}; q =（7,2）; return merged set = {（6,9），（7,2）}

征服：（8,6）（9,3）; M1 = {（8,6）}; M2 = {（9,3）}; q =（9,3）; return merged set = {（8,6），（9,3）}

征服：（6,9）（7,2）（8,6）（9,3）; M1 = {（6,9），（7,2）}; M2 = {（8,6），（9,3）}; q =（8,6）; return merged set = {（6,9），（8,6），（9,3）}

征服：（1,4）（2,6）（3,1）（4,5）（5,7）（6,9）（7,2）（8,6）（9,3）; L =（1,4）（2,6）（3,1）（4,5）（5,7）; M1 = {（5,7）}，M2 = {（6,9），（8,6），（9,3）}; q =（6,9）; return merged set = {（6,9），（8,6），（9,3）}

==>返回{（6,9），（8,6），（9,3）}