How to add `n log n` stones to a grid to form a beautiful arrangement using divide-and-conquer? - algorithm idea

Question

Beautiful Courtyard Arrangement

Our courtyard is a 10^9 by 10^9 grid. We have placed n stones at different integer coordinates to decorate our courtyard. However, the current arrangement is not beautiful. We have at most n log n additional stones to add to the arrangement in the courtyard. A beautiful arrangement is one where, for any two stones at coordinates (x_1, y_1) and (x_2, y_2), one of the following conditions is met:

1. They are in the same row (y_1 = y_2).
2. They are in the same column (x_1 = x_2).
3. There is a stone at coordinates (x_3, y_3) such that:
   • min(x_1, x_2) <= x_3 <= max(x_1, x_2)
   • min(y_1, y_2) <= y_3 <= max(y_1, y_2)

Your task is to determine how many additional stones to add and where to place them to achieve a beautiful arrangement in the courtyard. Please note the following:

1. Stones must be placed at integer coordinates.
2. Two stones cannot occupy the same position.
3. The initial stones are fixed.
4. You cannot use more than n log n additional stones.

We are not looking for the minimum number of stones to achieve a beautiful arrangement, just a solution with less than or equal to n log n additional stones. The order of printing the coordinates does not matter.

Input:

• The first line contains an integer n (2 <= n <= 2 * 10^4), the number of initial stones.
• The next n lines each contain two integers x_i and y_i (1 <= x_i, y_i <= 10^9), the coordinates of the i-th stone.

Output:

• First, print an integer m, the number of additional stones needed to achieve a beautiful arrangement.
• Then, in the next m lines, print the coordinates x_i and y_i of the stones to be added to the courtyard.

Sample Input 1:

4
1 1
1 2
2 1
2 2

Sample Output 1:

0

Sample Input 2:

5
1 1
1 3
3 1
3 3
2 2

Sample Output 2:

4
1 2
2 1
3 2
2 3

I believe that a divide-and-conquer approach may be suitable for addressing this challenge. I've experimented with various scenarios using recurrence and divide-and-conquer techniques, yet I'm struggling to devise an efficient algorithm with a time complexity of O(n log n). Given that it's possible to achieve O(n log n), I presume the algorithm would follow the form T(n) = kT(n/k) + Θ(n), indicating that we can break down the problem into n/k segments. However, I'm uncertain about how to implement this reduction and subsequently solve the issue. I would appreciate any suggestions, no matter how brief. Additionally, if there are pre-existing algorithms for this problem, sharing them would be immensely valuable.

Answer 1

First, sort the stones by x coordinate. We will use this same sorting throughout the entire algorithm.

1. Find the column that contains the median element, by x coordinate, so that there are <= N/2 stones on each side
2. Recursively fix the stones on each side. Now all the pairings on each side are valid, so only pairings that use or cross the chosen column can be invalid.
3. For each y coordinate that contains a stone on either side, make sure the chosen column contains a stone with the same y coordinate. Now there are no invalid pairings.

In step 3, since we only add stones to the chosen column, it only creates new pairings that use that column. It also ensures that every pairing that uses or crosses the chosen column is valid:

   | |               | |
o  | |         => o  |o|
   | |     o         |o|     o

o     | |        o     |o|
      | |   =>         | |
      |o|              |o|

Furthermore, the recursive operations on each side do not increase the number of stones that the parent operation has to add, because they don't introduce stones at any new y coordinates. As a result, there are at most N stones added at each of the ⌈log N⌉ levels, for a total of N⌈log N⌉.

To get this done in O(N log N) time, note that, after processing both sides in step 2, you do not need to process the new list of stones, which would be bigger than the original, because it doesn't introduce any new y coordinates. Process the original smaller list instead. Alternatively, process just the chosen columns on each side, because they use all y coordinates. Either way, there are a total of N nodes processed at each recursive level.