Home:ALL Converter>Efficient algorithm to find the largest rectangle from a set of points

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

Ask Time:2021-09-22T05:55:42         Author:Trevor2001

Json Formatter

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.

Author:Trevor2001,eproduced under the CC 4.0 BY-SA copyright license with a link to the original source and this disclaimer.
Link to original article:https://stackoverflow.com/questions/69275956/efficient-algorithm-to-find-the-largest-rectangle-from-a-set-of-points
David Eisenstat :

Yes, there's an O(n log n)-time algorithm (that should be matched by an element distinctness lower bound).\nIt 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.",
Zakk :

Say you have a rectangle formed by four points: A (top left), B (top right), C (bottom right) and D (bottom left).\nThe 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.\ndef nearest_point(origin, points):\n nearest = None\n mindist = dist(origin, points[0])\n\n for p in points[1:]:\n d = dist(origin, p)\n if mindist > d:\n mindist = d\n nearest = p\n\n return nearest\n\nCall it for B and D as origins:\npoints = [...]\n\np1 = nearest_point(B, points) # one for loop\np2 = nearest_point(D, points) # one for loop\n\nNote 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.",