The Strip Packing Problem is a classical optimization problem in which a given set of rectangles must be packed, without overlap, into a strip of fixed width and infinite height, while minimizing the total height of the packing. A straightforward and widely studied approach to this problem is the Bottom-Left Heuristic. It consists of iteratively placing each rectangle in the given order at the lowest feasible position in the strip and, in case of ties, at the leftmost of those. Due to its simplicity and good empirical performance, this heuristic is widely used in practical applications. The most efficient implementation of this heuristic was proposed by Chazelle in 1983, requiring $O(n^2)$ time and $O(n)$ space to place $n$ rectangles. However, although Chazelle's original description was largely correct, it omitted several formal details. Furthermore, our analysis revealed a critical flaw in the original runtime analysis, which, in certain cases, results in $Ω(n^3)$ running time. Motivated by this finding, this paper provides a rigorous and corrected presentation of the implementation, addressing the imprecise arguments and resolving the identified flaw. The resulting analysis establishes a formally verified version of Chazelle's implementation and confirms its quadratic time complexity.

翻译：条带装箱问题是一个经典的优化问题，其目标是将给定的一组矩形在无重叠的前提下，装入一个固定宽度、无限高度的条带中，同时最小化装箱的总高度。针对该问题，一种直接且被广泛研究的方法是Bottom-Left启发式算法。该算法按照给定顺序迭代放置每个矩形，将其置于条带中最低的可行位置，若存在多个最低位置，则选择其中最左侧的位置。由于其简单性和良好的实证性能，该启发式算法在实际应用中得到了广泛使用。该算法最高效的实现由Chazelle于1983年提出，其放置n个矩形的时间复杂度为$O(n^2)$，空间复杂度为$O(n)$。然而，尽管Chazelle的原始描述大体正确，但省略了若干形式化细节。此外，我们的分析揭示了原始运行时分析中存在一个关键缺陷，该缺陷在某些情况下会导致$Ω(n^3)$的运行时间。基于这一发现，本文对实现进行了严格且修正后的阐述，解决了原论述中的不精确之处并修正了已识别的缺陷。最终的分析建立了一个经过形式化验证的Chazelle实现版本，并确认了其二次时间复杂度。