Follow

Today at lunch, I've learned about the Trash Compaction problem: Can you push objects on a grid into the compact shape of a rectangle if you're only allowed to push all objects from one side simultaneously. Akitaya, Aloupis, Löffler, and Rounds showed that the problem is NP-complete.

The fun variant of this problem talks about pushing around coconuts with a giant coconut pusher... Here are some neat slides: http://www.staff.science.uu.nl/~loffl001/publications/slides/trash_compaction.pdf

natema@natema@mamot.fr@forster 😆