How fast can we play Tetris greedily with rectangular pieces?

DOI10.1016/J.TCS.2024.114405MaRDI QIDQ6149495zbMATH OpenOpenAlexWikidataFDO

Authors John Iacono

Publication date 5 March 2024

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2202.10771

zbMATH Keywords

axis-aligned rectanglesdynamic data structuresfine-grained complexityTetris

Mathematics Subject Classification ID

Theory of computing (68Qxx)

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 to the Multiphase problem [Pu{a}trac{s}cu, 2010] that on a board of width $w=Theta(n)$, if the OMv conjecture [Henzinger et al., 2015] is true, then both operations cannot be supported in time $O(n^{1/2-epsilon})$ 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}lo{g}^{3/2}n)$ time on boards of width $n^{O(1)}$, matching the lower bound up to a $n^{o(1)}$ factor.

Cites work

• A MIP approach for some practical packing problems: balancing constraints and tetris-like items
• A steganographic method based on tetris games
• Algorithms and computation. 8th international symposium, ISAAC '97, Singapore, December 17--19, 1997. Proceedings
• Answering UCQs under updates and in the presence of integrity constraints
• Artificial intelligence: Theories, models and applications. 6th Hellenic conference on AI, SETN 2010, Athens, Greece, May 4--7, 2010. Proceedings
• Color-distance oracles and snippets
• Combinatorial analysis of tetris-like games
• Conditional hardness for sensitivity problems
• Dynamic DFS in undirected graphs: breaking the \(O(m)\) barrier
• Dynamic geometric data structures via shallow cuttings
• Dynamic parameterized problems and algorithms
• Fast and Simple Connectivity in Graph Timelines
• Faster all-pairs shortest paths via circuit complexity
• From Tetris to polyominoes generation
• Gowers' Ramsey theorem for generalized tetris operations
• Higher lower bounds from the 3SUM conjecture
• scientific article; zbMATH DE number 7030641 (Why is no real title available?)
• scientific article; zbMATH DE number 2107521 (Why is no real title available?)
• scientific article; zbMATH DE number 7595810 (Why is no real title available?)
• scientific article; zbMATH DE number 6542806 (Why is no real title available?)
• Learning Tetris Using the Noisy Cross-Entropy Method
• Matching Triangles and Basing Hardness on an Extremely Popular Conjecture
• Mind the gap!
• More logarithmic-factor speedups for 3SUM, (median,+)-convolution, and some geometric 3SUM-hard problems
• Nearly optimal separation between partially and fully retroactive data structures
• On a class of \(O(n^ 2)\) problems in computational geometry
• On hardness of jumbled indexing
• On some fine-grained questions in algorithms and complexity
• On the hardness of partially dynamic graph problems and connections to diameter
• Performance bounds for policy iteration and application to the game of Tetris
• Reducibility among combinatorial problems
• Semi-Online Maintenance of Geometric Optima and Measures
• Subquadratic algorithms for 3SUM
• Tetris and decidability
• TETRIS IS HARD, EVEN TO APPROXIMATE
• Tetris is Hard, Even to Approximate
• Tetris: Using Software/Hardware Co-Design to Enable Handheld, Physics-Limited 3D Plane-Wave Ultrasound Imaging
• The complexity of theorem-proving procedures
• The reverse problem of range query
• Towards polynomial lower bounds for dynamic problems
• Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture
• Weighted fusion frame construction via spectral tetris

This page was built for publication: How fast can we play Tetris greedily with rectangular pieces?

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6149495)