Find a maximum rectangular area given an array of points

Question

Let's say I have an array of objects called Point.
Point object has x and y values.

To make it more difficult, let's say there are no initial boundaries which means the rectangular area we want to find are bounded by Point objects. So, there are at least 4 Point objects.

so if the array only has 4 Point objects: Point(0,0), Point(100,0) Point(0,100) and Point(100,100), we want to return 100*100, the rectangular area.

This is easy part. But think about situation where there are more than 4 Point objects. How do you find the maximum rectangular area?

public int maxArea(Point[] points)
{
    int area;
    //do algo
    return area;
}

EDIT: Just by looking at the min and max of y and x doesn't guarantee because im looking for the rectangular area that are free of Point objects. so there is nothing inside that maximum rectangle area

Answer 1

Let me first formulate the problem as I believe it was meant:

• The rectangle to be found has horizontal (constant y) and vertical (constant x) borders, i.e. no "rotations".

• The rectangle has at least one point on the 'internal' ('open') part of each of its edges, i.e. not at a corner. (it may have more than one point on any edge, and ALSO points at its corners.) This rules out the 'infinite' solutions, because all points have finite x,y. It also rules out the cases where we might intend to define the rectangle by only TopLeft and BottomRight points and similar constructs.

• we look for the rectangle with the maximum area among all that satisfy the above conditions.

Assuming the above to be a correct (re)formulation of the problem, I believe that it is a two-dimensional optimization problem with potentially many 'local' optima. Any approach of the type "start at something and gradually improve" will only find the local optimum, but not necessarily the global one.

I have not been able to come up with something better than a O(N^2) approach, involving - roughly speaking - N times a local optimization, where each local optimization is O(N). I'll sketch the method with some code snippets (partially pseudo-code or remarks) for the essential part of the local optimization. The remainder is "more of the same" and should not be difficult to fill in.

To cut down on wording without becoming inaccurate, henceforth I will mean by "a point on the edge (of a recctangle)" a point that is on the 'inner' part of the edge, not at a corner. Likewise, by 'rectangle' I will mean an "eligible" reactangle, i.e. one that satisfies the basic conditions: no points inside, and at least one point on each of its edges.

Now, the LOCAL optimization is "defined" by a specific point from the points-set, in combination with a specific "border-type" from {Left, Top, Right, Bottom}. Assume that we have chosen a point L and border-type "Left"; The locally optimal solution is defined as the 'best" (largest area) rectangle that has L on its Left edge.

We're going to construct all (L,Left)-rectangles and keep track of the largest one that we find on the way.

Observe: any (L,Left)-rectangle that has point R on its right border, must have a point T on its Top border and a point B on its bottomm border, where

L.x < T.x < R.x
L.x < B.X < R.X
B.y < L.y < T.y
B.y < R.y < T.Y

Image now, that we scan the points in x-ordered fashion, starting after L.

At the one hand: before we can find R, the above conditions show that we must first encounter T and B.

At the other hand, as soon as we've found R, from all the points with y > L.y that we've encountered in-between, we will by now be bounded by the one with the lowest y. and likewise for the bottom-border.

With N the number of points {P}, Let index_X[] be the array of indices for the x-sorted points, such that P[index_X[i]]x <= P[index_X[j]].x whenever i is less than j.

Furthermore, let iL be the index of L in the x-sorted array: P[index_X[iL]] = L.

In the following code-snippets (VB-syntax; it shouldn't be too difficult to translate in whatever language you use), we first determine "some" T (a top-edge point) and "some" B (a bottom-edge point). Then, we keep scanning, and whenever we find a point R that completes a rectangle, we: (a) calculate the area to update the optimum if it is larger; (b) replace T or B by the found R (depending on whether R is above L or below), and repeat the search for R.

    Dim indx As Integer = iL + 1 'first point to consider on the right of L
    Dim T As PointF = Nothing
    Dim B As PointF = Nothing
    ' find T,B
    While (indx < N AndAlso (T = Nothing OrElse B = Nothing))

      Dim Q As PointF = Pts(indx_X(indx))

      If (Q.Y > L.Y) Then
        ' a candidate for T
        If (T = Nothing) OrElse (Q.Y < T.Y) Then
          T = Q
        End If

      ElseIf (Q.Y < L.Y) Then
        ' a candidate for B
        If (B = Nothing) OrElse (Q.Y > B.Y) Then
          B = Q
        End If

      Else
        Return -1 'Failure for L altogether: Q has exactly the same y-value as L and we didn't find yet both T and B.
      End If

      indx += 1
    End While

    If (T = Nothing OrElse B = Nothing) Then
      Return -1  'Failure for L: we have exhausted all points on the right without finding both T and B.
    End If

    ' we have "some" T and B, now proceed to find all (L,Left) rectangles
    ' intialize result (= max area from (L,Left)-rectangles).
    Dim result As Double = -1
    ' the next point to consider
    indx += 1
    ' find successive rectangles, by searching for R, given L (fixed) and T,B (occasionally updated). 
    While (indx < N)

      Dim R As PointF = Pts(indx_X(indx)) 'candidate

      If (R.Y = L.Y) Then
        ' rectangle found, process it.
        Dim area As Double = (R.X - L.X) * (T.Y - B.Y)
        If area > result Then
          result = area
        End If
        ' it all stops here: no further rectangles {L,Left) are possible as they would have this R inside.
        Exit While
      End If

      If (R.Y > L.Y) Then
        ' a point with y > L.Y:
        ' if it is above T we can ignore it.
        ' if is below T, it is the R-bound for the rectangle bounded by L,T,B
        If (R.Y < T.Y) Then
          ' process the rectangle
          Dim area As Double = (R.X - L.X) * (T.Y - B.Y)
          If area > result Then
            result = area
          End If
          ' move on, understanding that for any NEXT rectangle this R must be the upperbound.
          T = R
        End If

      Else 'R.Y < L.Y
        ' a point with y < L.Y
        ' if it is below B we can ignore it.
        ' if it is above B, it is the R-bound for the rectangle bounded by L,T,B
        If (R.Y > B.Y) Then
          ' process the rectangle
          Dim area As Double = (R.X - L.X) * (T.Y - B.Y)
          If area > result Then
            result = area
          End If
          ' move on, understanding that for any NEXT rectangle this R must be the lowerbound.
          B = R
        End If

      End If

      indx += 1
    End While

    Return result

The overall solution is, of course: find for each point P, the optimum among opt(P,Left), opt(P,Right), opt(P,Top), opt(P,Bottom), and then find the maximum over all P. The varieties for Right, Top, Bottom are of course very similar to the opt(Left) that I sketched out above. The pre-sorting (to get indices for x-order and for y-order (for handling the (P,Top) and (P,Bottom)-cases) are O(nLogn), the local optimizations are each O(n) - view the code. So the overall complexity is O(n^2).

Note added - because the original formulation was not absolutely clear to me: IF rectangles can also be bounded by CORNER-points, then the above needs a few minor adjustments (mostly adding equal signs to inequality conditions), but it won't change the algorithm in essence.