首先，我认为问题的表述应该是这样的：
要找到的矩形有水平（恒定y）和垂直（恒定x）的边界，即没有“旋转”。
矩形至少在每条边的“内部”（“打开”部分）上有一个点，不在角落处。
（它可能在任何边上有多个点，并且也可能在其角落处有点。）
这排除了“无限”解决方案，因为所有点都有有限的x，y。
它还排除了我们可能想要仅通过左上角和右下角点以及类似结构来定义矩形的情况。
我们要在满足上述条件的所有矩形中寻找面积最大的矩形。
假设上述是问题的正确（重新）表述，我认为这是一个二维优化问题，可能有许多“局部”最优解。
任何类型的“从某个地方开始逐渐改进”的方法都只会找到局部最优解，但不一定是全局最优解。
我没有能够想出比O(N^2)更好的方法，大致需要N次本地优化，其中每个本地优化为O(N)。
我将用一些代码片段（部分伪代码或备注）草图来说明本地优化的基本部分。
其余部分是“更多的相同”，应该不难填写。
为了减少文字而不变得不准确，从现在开始，“边缘上的点（矩形的边缘）”指的是在边缘的“内部”部分的点，而不是在角落处。
同样，通过“矩形”，我将指一个“有资格”的矩形，即满足基本条件的矩形：没有内部点，并且每条边上至少有一个点。
现在，局部优化是由来自点集的特定点以及{Left，Top，Right，Bottom}中的特定“边框类型”共同“定义”的。
假设我们选择了一个点L和边框类型“Left”；局部最优解被定义为具有L在其左边缘的“最佳”（最大面积）矩形。
我们将构建所有（L，Left）-矩形，并在途中跟踪找到的最大矩形。
请注意：任何（L，Left）-矩形，其右边缘上有点R，必须具有点T和B在其顶部和底部边界上，其中
L.x < T.x < R.x
L.x < B.X < R.X
B.y < L.y < T.y
B.y < R.y < T.Y
假设我们按照x顺序扫描点，从L之后开始。
一方面，在找到R之前，上述条件表明我们必须先遇到T和B。
另一方面，一旦我们找到R，从所有y > L.y的点中，我们在中间遇到的点现在将被最低y值所限制。底部边界同理。
假设N是点{P}的数量，
让index_X[]成为按x排序的点的索引数组，使得当i小于j时，P [index_X [i]] x <= P [index_X [j]].x。
此外，让iL成为x排序数组中L的索引：P [index_X [iL]] = L。
在以下代码片段（VB语法；无论您使用什么语言，都不应该太难进行翻译）中，我们首先确定“某个”T（顶部点）和“某个”B（底部点）。
然后，我们继续扫描，并且每当找到一个完成矩形的点R时，我们：
(a) 计算要更新的最优解的面积（如果更大）；
(b) 用找到的R替换T或B（取决于R是否在L上方），并重复查找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
总体解决方案当然是：对于每个点P，找到opt(P, Left)，opt(P, Right)，opt(P, Top)，opt(P, Bottom)中的最优解，然后在所有P中找到最大值。
对于Right，Top和Bottom的变量当然与我上面概述的opt(Left)非常相似。
预排序（为了获取x-order和y-order的索引（用于处理（P，Top）和（P，Bottom）情况））是O(nLogn)，每个本地优化都是O(n)-查看代码。因此，总体复杂度为O(n^2)。
注：由于原始表述对我来说不是绝对清晰：
如果矩形也可以由CORNER点限定，则以上需要进行一些微小的调整（主要是向不等式条件添加等号），但本质上不会改变算法。
