Shotgun Assembly of Random Jigsaw Puzzles

Original · EN

In a recent work, Mossel and Ross considered the shotgun assembly problem for a random jigsaw puzzle. Their model consists of a puzzle - an n× n grid, where each vertex is viewed as a center of a piece. They assume that each of the four edges adjacent to a vertex, is assigned one of q colors (corresponding to "jigs", or cut shapes) uniformly at random. Mossel and Ross asked: how large should q = q(n) be so that with high probability the puzzle can be assembled uniquely given the collection of individual tiles? They showed that if q = ω(n²), then the puzzle can be assembled uniquely with high probability, while if q = o(n²/³), then with high probability the puzzle cannot be uniquely assembled. Here we improve the upper bound and show that for any > 0, the puzzle can be assembled uniquely with high probability if q ≥ n1+. The proof uses an algorithm of nΘ(1/) running time.