How does recursion work in a divide and conquer maxima set algorithm?

Question

Here is a pseudo code algorithm from an algorithm textbook by Goodrich for finding the dominating 2D points in a set of points, known as finding maxima sets:

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

My question is in the two recursive calls at line 10,11. My understanding is that the first calls for M1 at line 10 will break the L side into another L and G set, and then the next L into another L and G set, until one set remains, the the next line will run and do the same thing to the G side for M2, but now how does it do the comparisons with q? Can someone help me trace the conquer part of this algorithm?

Given

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

I know the maxima set is (6,9) (8,6) (9,3) but I am stuck on how exactly that came to light using THIS algorithm. I solved it via brute force. This started as a HW question, and I technically can move on because I did find the answer, but I really need to get an understanding of this and I've tried 2 textbooks and google but I think I need a person this time. Thank you in advance and since this is my first time on stack please don't hesitate to (kindly, please) give me any corrections to how I asked my question or presented my p-code

Answer 1

The idea of the conquer part is that, you have to assumed the returned set M1 & M2 fulfilled this condition:

Any pair of points in the same set can be co-existing

That is, any pair of the points in the set must fulfilled x1 < x2 && y1 > y2

And after you merge M1 and M2, you should return a set fulfilling this condition too, and at last the set we obtain is the answer.

One point to note that is, I think when merging, x is actually not needed to be compared, as all points in M1 should have x <= than those in M2

---

We use q, the first point in M2 to compared with all points in M1, because

1. As mentioned, q does not need to compared with other elements in M2
2. Visually, q is the point with smallest x and largest y in M2, as mentioned, all M1's x should be smaller than all points in M2, so the main point here is q has largest y in M2, thus the largest "potential" to cover (elminitate) points in M1

Combined 1 & 2, the algorithm uses q to compare all points in M1 to try to eliminate hopeless candidates, and union those left with M2 to form a new set which fulfilled mentioned condition.

---

Let's do a demo using your example:

Divide: (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)

Divide: (1,4) (2,6) (3,1) (4,5) (5,7); L = (1,4) (2,6), (3,1); R = (4,5) (5,7)

Divide: (1,4) (2,6) (3,1); L = (1,4) (2,6); R = (3,1), Return {(3,1})

Divide: (1,4) (2,6); L = (1,4); Return {(1,4)}; R = (2,6); Return {(2,6)}

Divide: (4,5) (5,7); L = (4,5); Return {(4,5)}; R = (5,7); Return {(5,7)}

Conquer: (1,4) (2,6); M1 = {(1,4)}; M2 = {(2,6)} q = (2,6); return merged set = {(2,6)}

Conquer: (1,4) (2,6) (3,1); M1 = {(2,6)}; M2 = {(3,1)}; q = (3,1); return merged set = {(2,6), (3,1)}

Conquer: (4,5) (5,7); M1 = {(4,5)}; M2 = {(5,7)}; q = (5,7); return merged set = {(5,7)}

Conquer: (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)}

Divide: (6,9) (7,2) (8,6) (9,3); L = (6,9) (7,2); R = (8,6) (9,3)

Divide: (6,9) (7,2); L = (6,9); Return {(6,9}); R = (7,2); Return {(7,2)}

Divide: (8,6) (9,3); L = (8,6); Return {(8,6)}; R = (9,3), Return {(9,3)}

Conquer: (6,9) (7,2); M1 = {(6,9)}; M2 = {(7,2)}; q = (7,2); return merged set = {(6,9), (7,2)}

Conquer: (8,6) (9,3); M1 = {(8,6)}; M2 = {(9,3)}; q = (9,3); return merged set = {(8,6), (9,3)}

Conquer: (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)}

Conquer: (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)}

==> Return {(6,9), (8,6), (9,3)}