algorithm - 如何在高度图中找到体积最大的长方体？ (复杂度低)

Question

我需要找到包含在 2D 高度图中的体积最大的长方体。高度图是一个大小为 w*d 的数组，其中 w 是宽度，h 是高度，d 是深度。在 C 语言中，这看起来类似于:

unsigned heightmap[w][d]; // all values are <= h

我已经知道有一种简单的算法可以以 O(w*d*h) 复杂度解决这个问题。但是，我怀疑存在更优化的方法。它的工作原理如下，采用 Python 伪代码:

resultRectangle = None
resultHeight = None
resultVolume = -1

# iterate over all heights
for loopHeight in range(0, h):
    # create a 2D bitmap from our heightmap where a 1 represents a height >= loopHeight
    bool bitmap[w][d]
    for x in range(0, w):
        for y in range(0, d):
            bitmap[x][y] = heightmap[x][y] >= loopHeight

    # obtain the greatest-volume cuboid at this particular height
    maxRectangle = maxRectangleInBitmap(bitmap)
    volume = maxRectangle.area() * loopHeight

    # compare it to our current maximum and replace it if we found a greater cuboid
    if volume > resultVolume:
        resultHeight = loopHeight
        resultVolume = volume
        resultRectangle = maxRectangle

resultCuboid = resultRectangle.withHeight(resultHeight)

查找矩形中所有 1 的最大面积是一个已知问题，每个像素的复杂度为 O(1) 或 O(w*d) 在我们的例子中。因此，朴素方法的总复杂度为 O(w*h*d)。

正如我已经说过的，我想知道我们是否可以克服这种复杂性。也许我们可以通过更智能地搜索高度而不是“暴力破解”所有高度来将其降低到O(w*d * log(h))。

这个问题的答案Find largest cuboid containing only 1's in an NxNxN binary array Evgeny Kluev 似乎采取了类似的方法，但它错误地(？)假设我们在这些高度找到的体积形成单峰函数。如果是这样的话，我们可以使用黄金分割搜索来更智能地选择高度，但我认为我们做不到。

Answer 1

这是一个带有重要假设的想法。伪代码:

P <- points from heightmap sorted by increasing height.
R <- set of rectangles. All maximal empty sub-rectangles for the current height.
R.add(Rectangle(0,0,W,H)
result = last_point_in(P).height()
foreach(p in P):
   RR <- rectangles from R that overlap P (can be found in O(size(RR)), possibly with some logarithmic factors)
   R = R - RR
   foreach(r in RR)
       result = max(result, r.area() * p.height())
       split up r, adding O(1) new rectangles to R.
return result

我有一种直觉，但无法证明的假设是 RR 的平均大小为 O(1)。

编辑:澄清“ split ”，如果我们在点 p split :

AAAAADFFF
AAAAADFFF
AAAAADFFF
BBBBBpGGG
CCCCCEHHH
CCCCCEHHH

我们生成新的矩形，其中包含:ABC、CEH、FGH、ADF，并将它们添加到 R 中。