# Find axis-aligned rectangle with maximum area in a point set in the Euclidean plane

On the plane $$n$$ points $$(x_i, y_i)$$ are marked. Select 4 points so that they define a rectangle with the greatest area and sides parallel to the axes.

Time limit for python is 10 seconds, for other programming languages - 2 seconds.

Input data:

• in first string integer $$n$$, $$(4 \leq n \leq 3000)$$
• in next $$n$$ strings pairs of integer coordinates $$x_i\ y_i$$ $$(-10\ 000 \leq x_i,\ y_i \leq 10\ 000)$$

Output data:

• 4 different indices (numbers from $$1$$ to $$n$$), specifying the vertices of the rectangle.

I made in python, but even with tests of $$n \leq 111$$ it have TL.

n = int(input())
l = []
for i in range(n):
a, b = map(int, input().split())
l.append((a, b))

ans = [1, 2, 3, 4]
mS = 0

for i in range(0, n - 3):
for j in range(i, n - 2):
for k in range(j, n - 1):
for t in range(k, n):
r = [l[i], l[j], l[k], l[t]]
w = sorted(r, key=lambda element:(element[0], element[1]))
if w[0][0] == w[1][0] and w[1][1] == w[3][1] and w[3][0] == w[2][0] and w[2][1] == w[0][1]:
s = (w[1][1] - w[0][1]) * (w[3][0] - w[1][0])
if s > mS:
mS = s
ans = [i + 1, j + 1, k + 1, t + 1]

ans = sorted(ans)
print(ans[0], ans[1], ans[2], ans[3])

• Can you put the reference to the original problem and explain properly how 4 points should define the rectangle. Do they have to be the 4 corners ? If you can also replace your python code with pseudo-code or just explain your method (even if it is simple brute-force), it would be perfect. Commented Jun 7, 2019 at 14:49
• @Vince I can't put the link, the competition is closed. Right, my code just simple brute-force. It takes each 4 points and check does it rectangle with sides parallel to axes. This task does not go out of my head. I think there is some kind of algorithm to reduce the complexity of calculations. And points should be the 4 corners, yes. Commented Jun 7, 2019 at 14:54
• Okay without a link you can tell which competition it is so people can check it is actually closed. Commented Jun 7, 2019 at 15:01
• Commented Jun 7, 2019 at 15:03
• I don't see any question, here. Note also that questions about coding are off-topic, here. Commented Jun 7, 2019 at 15:42

Step 1. Sort all the points according to their $$x$$-coordinate - you will get an array of buckets, where each bucket contains a (sorted) list of points with the same $$x$$-coordinate. You can drop (or ignore in all subsequent steps) all the buckets, containing only single point.

Step 2. Define a mapping $$M$$, where the key will be a closed integer interval and the value - ordered set of integers. Scan all the buckets, created in the Step 1. For each bucket insert all the possible pairs of its $$y$$-coordinates into the mapping $$M$$ - their corresponding $$x$$-coordinates must be inserted into the set, corresponding to this interval:

function Insert(M, x, y0, y1)
if mapping M contains element ([y0, y1] -> S)
insert x into set S
else
insert element ([y0, y1] -> (x)) into mapping M


You can drop (or ignore in all subsequent steps) all the elements of the mapping $$M$$, for which their value set contains only a single number.

Step 3. The mapping M will contain elements like this:

$$([y_0, y_1] \rightarrow (x_0, x_1, ..., x_{m-1}))$$

The biggest rectangle with "vertical" side $$[y_0, y_1]$$ will have "horizontal" side $$[x_0, x_{m-1}]$$, so you can ignore all the middle elements of the ordered set. Finally, scan all the elements in the $$M$$ to find the element with largest rectangle area $$A$$:

$$A = (y_1 - y_0) \cdot (x_{m-1} - x_0)$$

Number of intervals in $$M$$ is $$O(n^2)$$, so time to insert into the mapping will be $$O(n^2log(n))$$.

Sort the points indexes on increasing $$x_i$$ (time complexity $$O(N\log N)$$). Then, with one loop on this sorted list, you can create the following structure:

• $$GX$$, list of sublists where points in the same sublist share the same $$x$$ value.
• $$AX$$, array of size $$n$$ giving for any $$i$$ the index of the sublist that contains $$i$$ in $$GX$$.

Once it is done, sort every sublist of $$GX$$ on increasing $$y$$

Let's do the same for $$y$$, to obtain $$GY$$ and $$AY$$. So far time complexity is still $$O(N\log N)$$.

A valid rectangle of four points $$a, b, c, d$$ starting up left clockwise should have:

• $$AX[a] = AX[d]$$
• $$AX[b] = AX[c]$$
• $$AY[a] = AY[c]$$
• $$AY[b] = AX[d]$$

Now, let's do the nested loops using $$GX$$ and $$GY$$ to hardly reduce the number of rectangles to check:

• Loop on all possible $$a$$
• Loop on all $$b$$ in $$GY[AY[a]]$$
• create two pointers $$c$$ and $$d$$ in respectively $$GX[AX[b]]$$ and $$GX[AX[a]]$$
• evaluate in linear time all possible $$c, d$$ such that $$y[c] = y[d]$$ (it is possible as the GX are sorted by $$y$$)

Complexity should be $$O(N^2)$$, I am not sure about that.

As all the sublists are sorted, you can also know the maximum array reachable from the upper left corner in $$O(1)$$. So check the potentially large rectangles first and use a stop criterion.

You finally have a $$O(N^2)$$ complexity instead of your $$O(N^4)$$.

• Two possible enhancements: First, eliminate all points with a unique x-coordinate or a unique y-coordinate, which then might lead to the elimination of more points. Second, iterate in an order that tends to find large areas first: In the first two loops, a and b must be in the same list with k elements. Iterate over a and b that are k-1 apart, then k-2 apart etc., this will tend to have a long side first. If you found a solution already, you may be able to proof that you can't find a rectangle with the side (a, b) and a larger area. Otherwise, ... Commented Jun 8, 2019 at 19:16
• ... when you iterate through the points c, d, you start with the points furthest away from a and b, and stop iterating once you know that the area of (a, b, c, d) cannot break the record so far. Commented Jun 8, 2019 at 19:17
• @gnasher729 absolutely, that is what I meant when I said check the largest rectangles first. I did not want to give all these precisions as it does not change time complexity and would make a lot harder my answer to understand. Commented Jun 8, 2019 at 19:50