论文标题
我们可以用矩形碎片贪婪地玩俄罗斯方块？
How Fast Can We Play Tetris Greedily With Rectangular Pieces?
论文作者
论文摘要
考虑在宽度$ w $和无限高度的板上播放的俄罗斯方块的变体，其中零件是任意整数尺寸的轴线对准矩形，只能在让它们掉落之前移动碎片，而一旦它填满，则行不消失。假设我们要遵循一种贪婪的策略：让每个矩形落在董事会当前状态下最终最低的地方。为此，我们想要一个数据结构，该数据结构总是可以暗示贪婪的举动。换句话说，我们想要一个数据结构，该数据结构维护一组$ O（n）$矩形，支持返回降低矩形的查询，并更新插入矩形以某个位置下降并返回更新的矩形集合中最高点的高度。我们通过减少对多相问题的减少[Pătraşcu，2010年]表明，如果OMV猜想[Henzinger等，2015]是正确的，那么在宽度$ w =θ（n）$的板上都是正确的，那么这两个操作都不能在时间$ o（n^{1/2-ε}）$同时支持。还原还意味着来自3-SUM猜想和APSP猜想的多项式边界。另一方面，我们表明有一个数据结构支持$ O（n^{1/2} \ log^{3/2} n）$ n^{o（1）} $的两个操作，匹配下部的下部限制至$ n^{o（1）} $。
Consider a variant of Tetris played on a board of width $w$ and infinite height, where the pieces are axis-aligned rectangles of arbitrary integer dimensions, the pieces can only be moved before letting them drop, and a row does not disappear once it is full. Suppose we want to follow a greedy strategy: let each rectangle fall where it will end up the lowest given the current state of the board. To do so, we want a data structure which can always suggest a greedy move. In other words, we want a data structure which maintains a set of $O(n)$ rectangles, supports queries which return where to drop the rectangle, and updates which insert a rectangle dropped at a certain position and return the height of the highest point in the updated set of rectangles. We show via a reduction to the Multiphase problem [Pătraşcu, 2010] that on a board of width $w=Θ(n)$, if the OMv conjecture [Henzinger et al., 2015] is true, then both operations cannot be supported in time $O(n^{1/2-ε})$ simultaneously. The reduction also implies polynomial bounds from the 3-SUM conjecture and the APSP conjecture. On the other hand, we show that there is a data structure supporting both operations in $O(n^{1/2}\log^{3/2}n)$ time on boards of width $n^{O(1)}$, matching the lower bound up to a $n^{o(1)}$ factor.
