2. Overview
As in the work of Wolfson et al. [21], our algorithm first assembles the border pieces using a heuristic for the traveling salesman problem.
We depart from previous work in how we place the interior pieces.
Because we do not assume that pieces have well-defined sides, we require a more global matching technique.
At all times, we maintain an optimized planar embedding of the current partial solution.
We fit a piece into a pocket not by independent pairwise fitting with top and side neighbors as in [21], but by fitting it into the embedded partial solution, thus allowing for any number of neighbors around the pocket.
Wolfson et al. rejected global embedding because of the possibility of accumulated errors, but we found to the contrary that global embedding gave more accurate results than pairwise matching, enabling a greedy placement algorithm—without any backtracking or branch-and-bound—to solve the
jigsaw puzzles.
(For more complicated puzzles, we could easily add backtracking or branch-and-bound.)