1. Let s be the rectangle from Pr(t) with the right lower corner c that ends. Since s intersects all polygons from c up to the upper boundary or r (t), the removal of s decreases the cover-variables by one for all polygons above c, the two polygons adjacent to c have to join, and the maximal polygons above c have to be output. The join-operation can be done by updating list L after locating the two polygons by binary search for c. The output operation can be performed easily by scanning list LM from the top until the y-coordinate of c has been reached.