License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FUN.2022.13
URN: urn:nbn:de:0030-drops-159839
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/15983/
Dallant, Justin ;
Iacono, John
How Fast Can We Play Tetris Greedily with Rectangular Pieces?
Abstract
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.
BibTeX - Entry
@InProceedings{dallant_et_al:LIPIcs.FUN.2022.13,
author = {Dallant, Justin and Iacono, John},
title = {{How Fast Can We Play Tetris Greedily with Rectangular Pieces?}},
booktitle = {11th International Conference on Fun with Algorithms (FUN 2022)},
pages = {13:1--13:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-232-7},
ISSN = {1868-8969},
year = {2022},
volume = {226},
editor = {Fraigniaud, Pierre and Uno, Yushi},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/15983},
URN = {urn:nbn:de:0030-drops-159839},
doi = {10.4230/LIPIcs.FUN.2022.13},
annote = {Keywords: Tetris, Fine-grained complexity, Dynamic data structures, Axis-aligned rectangles}
}
|
Keywords: |
|
Tetris, Fine-grained complexity, Dynamic data structures, Axis-aligned rectangles |
|
Collection: |
|
11th International Conference on Fun with Algorithms (FUN 2022) |
|
Issue Date: |
|
2022 |
|
Date of publication: |
|
23.05.2022 |
