How fast can we play Tetris greedily with rectangular pieces?

DOI10.1016/J.TCS.2024.114405arXiv2202.10771OpenAlexW4391179638WikidataQ129455032 ScholiaQ129455032MaRDI QIDQ6149495FDOQ6149495

Authors: John Iacono 

Publication date: 5 March 2024

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

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.

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

zbMATH Keywords

dynamic data structuresTetrisfine-grained complexityaxis-aligned rectangles

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

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

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)