Trash Compaction

Let P be a set of n objects on a square grid. A push is a transformation of P that involves sweeping a horizontal or vertical line by one unit, starting from the hull of P. The sweep displaces objects that are in contiguous positions. For example, when pushing to the right, all the leftmost objects are displaced one unit to the right. This in turn displaces other objects further right. Given P, we want to find a sequence of pushes that will produce a rectangle of a given height and width. We show that deciding whether a square can be produced is NP-hard, but it takes polynomial time to decide if a rectangle of height 2 can be produced.

keywords: Computational Geometry, Fixed-Parameter Tractability, Puzzles

Workshop or Poster (weakly reviewed)

Anika Rounds, Greg Aloupis, Hugo Akitaya, Maarten Löffler
Trash Compaction
Proc. 32nd European Workshop on Computational Geometry
107–110, 2016

back to list