We actually talked about this paper in class. And, inspired by it, I later wrote a homework assignment explaining why jigsaw puzzles are NP-complete. Most of the rest of the class decided they were O(n²), but I defined "jigsaw puzzle" in a more interesting way.