slides
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.