Shotgun assembly of random jigsaw puzzles

DOI10.1002/RSA.20899MaRDI QIDQ5128750zbMATH OpenOpenAlexWikidataFDO

Authors Charles Bordenave, Elchanan Mossel, Uriel Feige

Publication date 26 October 2020

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1605.03086

zbMATH Keywords

exact recoveryplanted solutionunique reconstruction

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (05C99) Combinatorial probability (60C05)

Abstract: In a recent work, Mossel and Ross considered the shotgun assembly problem for a random jigsaw puzzle. Their model consists of a puzzle - an $nimesn$ 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=omega(n^2)$, then the puzzle can be assembled uniquely with high probability, while if $q=o(n^{2/3})$, then with high probability the puzzle cannot be uniquely assembled. Here we improve the upper bound and show that for any $eps>0$, the puzzle can be assembled uniquely with high probability if $qgeq{n}^{1+eps}$. The proof uses an algorithm of $n^{Theta(1/eps)}$ running time.

Recommendations

• A Linear Threshold for Uniqueness of Solutions to Random Jigsaw Puzzles
• Unique reconstruction threshold for random jigsaw puzzles
• No easy puzzles: hardness results for jigsaw puzzles
• Shotgun assembly of Erdős-Rényi random graphs
• A global approach to automatic solution of jigsaw puzzles

Cites work

• A congruence theorem for trees
• scientific article; zbMATH DE number 3458693 (Why is no real title available?)
• Information Theory of DNA Shotgun Sequencing
• Percolation

Cited in

(10)

• Shotgun assembly of Erdős-Rényi random graphs
• Shotgun identification on groups
• No easy puzzles: hardness results for jigsaw puzzles
• Solving jigsaw puzzles by the graph connection Laplacian
• Unique reconstruction threshold for random jigsaw puzzles
• Shotgun reconstruction in the hypercube
• Shotgun assembly threshold for lattice labeling model
• Shotgun assembly of Linial-Meshulam model
• Shotgun assembly of unlabeled Erdős-Rényi graphs
• Reconstructing random pictures

This page was built for publication: Shotgun assembly of random jigsaw puzzles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5128750)