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

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.

CodePudding user response：

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.

CodePudding user response：

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.

CodePudding user response：

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)).