Abstract
We propose a novel mathematical framework to address the problem ofautomatically solving large jigsaw puzzles. This problem assumes a large imagewhich is cut into equal square pieces that are arbitrarily rotated and shuffledand asks to recover the original image given the transformed pieces. The maincontribution of this work is a theoretically-guaranteed method for recoveringthe unknown orientations of the puzzle pieces by using the graph connectionLaplacian associated with the puzzle. Iterative application of this method andother methods for recovering the unknown shuffles result in a solution for thelarge jigsaw puzzle problem. This solution is not greedy, unlike many othersolutions. Numerical experiments demonstrate the competitive performance of theproposed method.