2026-08-02T21:47:43Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:15983 2024-03-06T10:57:00Z ddc:004 open_access

How Fast Can We Play Tetris Greedily with Rectangular Pieces? Dallant, Justin Iacono, John Tetris Fine-grained complexity Dynamic data structures Axis-aligned rectangles 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 from 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 an n^o(1) factor. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Justin Dallant and John Iacono 2022 Is Part Of LIPIcs, Volume 226, 11th International Conference on Fun with Algorithms (FUN 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FUN.2022.13 urn:nbn:de:0030-drops-159839 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.13 eng https://creativecommons.org/licenses/by/4.0/legalcode