Efficient algorithm to find the largest rectangle from a set of points

Question

I have an array of points, and my goal is to pick two so that I maximize the area of the rectangle formed by the two points (one representing the low left corner and the other one the right top corner).

I could do this in O(n^2) by just doing two for loops and calculating every single possible area, but I think there must be a more efficient solution:

max_area = 0
for p1 in points:
    for p2 in points:
       area = p2[0]p2[1] + p1[0]p1[1] - p2[1]p1[0] - p2[0]p1[1]
       if area > max_area:
           max_area = area

It's clear that I want to maximize the area of the second point with the origin (0,0) (so p2[0]p2[1]), but I'm not sure how to go forward with that.

Barrage

Can you please post what have you tried til now? – Gramicidin

yes, sorry, I added some more info – Barrage

On inspection, seems like a problem that would benefit from spacial partitioning. Maybe k-d trees? – Sabir

Answer 1

Yes, there's an O(n log n)-time algorithm (that should be matched by an element distinctness lower bound).

It suffices to find, for each p1, the p2 with which it has the largest rectangular area, then return the overall largest. This can be expressed as a 3D extreme point problem: each p2 gives rise to a 3D point (p2[0], p2[1], p2[0] p2[1]), and each p1 gives rise to a 3D vector (-p1[0], -p1[1], 1), and we want to maximize the dot product (technically plus p1[0] p1[1], but this constant offset doesn't affect the answer). Then we "just" have to follow Kirkpatrick's 1983 construction.

Howund

What about A minimalist's implementation of the 3-d divide-and-conquer convex hull algorithm (2003) by Timothy M. Chan ? The paper mentions that the "algorithm is particularly suitable for answering 3-d extreme point queries." There's at least one code implementation shared online but applied to a different problem. – Rowlandson

this is a neat trick – Lashundalasker

Answer 2

Divide and conquer.

Note: This algorithm presumes that the rectangle is axis-aligned.

• Step 1: Bucket the points into a grid of 4x4 buckets. Some buckets may get empty.
• Step 2: Using the corners of the buckets, calculate maximum areas by opposite corners between not empty buckets. This may result in several pairs of buckets, because your work with corners, not points.
  Notice also that you use left corners for left buckets, and so for bottom, right, top corners for those b,r,t buckets. That's why an even number is used for the size of the grid.
• Step 3: Re-bucket each bucket selected in step 2 as a new, smaller, 4x4 grid.
• Repeat steps 2 & 3 until you get only a pair of buckets that contain only a point in each bucket.

I have not calculated the complexity of this algorithm. Seems O(n log(n)).

Anthropologist

The distance is not sufficient to find the best solution. I think your algorithm is good to find the rectangle with the biggest perimeter (linear) but not the biggest area (non-linear). – Showcase

I've edited my answer to calculate areas instead of distances. – Anthropologist

Answer 3

Say you have a rectangle formed by four points: A (top left), B (top right), C (bottom right) and D (bottom left).

The idea is to find two points p1 and p2 that are the closest to B and D respectively. This means that p1 and p2 are the furthest possible from each other.

def nearest_point(origin, points):
    nearest = None
    mindist = dist(origin, points[0])

    for p in points[1:]:
        d = dist(origin, p)
        if mindist > d:
            mindist = d
            nearest = p

    return nearest

Call it for B and D as origins:

points = [...]

p1 = nearest_point(B, points)  # one for loop
p2 = nearest_point(D, points)  # one for loop

Note that there can be multiples closest points which are equally distant from the origin (B or D). In this case, nearest_point() should return an array of points. You have to do two nested for loops to find the furthest two points.

Gramicidin

I think this method have the same problem than the one of Ripi2 (see my comment). The algorithm will likely optimize the perimeter and nor the area. – Showcase

@JérômeRichard: not even the perimeter. And "the furthest possible from each other" is not true. – Aintab

@YvesDaoust Why isn't it true? – Gramicidin

It is not difficult to find configurations such that P1 and P2 are the closest to B and D, but there are other points that are furthest from each other. (For instance points very close to A and C.) – Aintab

@YvesDaoust OP's question is: maximize the area of the rectangle formed by the two points (one representing the low left corner and the other one the right top corner). – Gramicidin

@YvesDaoust Of course you can do the same thing for A and C. Just the OP's question is about B and D. But the idea is the closest points to the edge points form the largest rectangles. – Gramicidin

I am commenting on your answer, and your question in the comments. And it is still possible to find such configurations with points near B and D. – Aintab