pith. sign in

arxiv: 2008.07644 · v3 · submitted 2020-08-17 · 💻 cs.CV · cs.AI· cs.CG

Pictorial and apictorial polygonal jigsaw puzzles from arbitrary number of crossing cuts

Peleg Harel Ofir Itzhak Shahar , Ohad Ben-Shahar This is my paper

Pith reviewed 2026-05-24 13:47 UTC · model grok-4.3

classification 💻 cs.CV cs.AIcs.CG
keywords jigsaw puzzlepolygonal piecesspring-mass dynamicsloop constraintsautomatic assemblyapictorial puzzlespictorial puzzlesfragment reconstruction
0
0 comments X

The pith

Polygonal jigsaw puzzles generated by arbitrary crossing cuts can be solved automatically by abstracting them as a spring-mass dynamical system with hierarchical loop constraints.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper introduces puzzles whose pieces are convex polygons formed by slicing a global shape with any number of straight cuts. It shows that these puzzles, including versions with image content on the pieces, remain solvable even after realistic noise is added to the piece boundaries. The solution models the pieces as interacting bodies in a spring-mass system that respects hierarchical loop constraints during a layered reconstruction. A sympathetic reader would care because most prior puzzle solvers assumed identical square pieces, while real fragments from broken objects are irregular polygons.

Core claim

The paper claims that abstracting the assembly of these crossing-cut polygonal pieces as a multi-body spring-mass dynamical system endowed with hierarchical loop constraints and a layered reconstruction process renders the puzzles solvable completely automatically, both when the pieces carry no pictorial information and when they do.

What carries the argument

A multi-body spring-mass dynamical system endowed with hierarchical loop constraints and a layered reconstruction process that simulates piece interactions to recover the global assembly.

If this is right

  • Puzzles created with an arbitrary number of crossing cuts become tractable despite their combinatorial complexity.
  • Both apictorial puzzles and pictorial puzzles on the same polygonal pieces admit automatic solutions.
  • Geometrical noise in piece boundaries does not prevent correct reconstruction under the proposed constraints.
  • Defined evaluation metrics can quantify the quality of the automatic assemblies produced.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same spring-mass formulation with loop constraints could be tested on fragment-assembly tasks outside jigsaw puzzles, such as reassembling scanned shards of pottery.
  • Varying the number of cuts while keeping noise fixed would reveal whether the layered reconstruction scales without additional tuning.
  • The hierarchical constraints may implicitly reduce the search space enough to avoid many local minima that plague purely combinatorial matchers.

Load-bearing premise

The spring-mass simulation with loop constraints will converge to the globally correct assembly even when piece geometry is contaminated by realistic noise.

What would settle it

A run of the spring-mass simulation on a set of noisy pieces from a known original polygon that fails to reach the correct global configuration.

Figures

Figures reproduced from arXiv: 2008.07644 by Ohad Ben-Shahar, Peleg Harel Ofir Itzhak Shahar.

Figure 1
Figure 1. Figure 1: The type of visual puzzle classes most studied in the literature. Shown are both the bag of pieces and the reconstructed puzzle. Sketched are only apictorial puzzles of the same global (in this case, rectangular) shape to emphasize the effect of the class on the possible geometry of the pieces. A: Commercial toy puzzle. B: Square Jigsaw puzzle. Note that while the sketch focuses on their geometry, these pu… view at source ↗
Figure 2
Figure 2. Figure 2: The elements of a crossing cuts puzzle. A: The puzzle is created by cutting a convex polygon using multiple (here 3) straight lines. B: The puzzle problem constitutes of an un-ordered and arbitrarily transformed set of pieces. Note that different pieces may vary vastly in size (e.g., compare pieces pB and pD. C: The mating graph matches pairs of edges of two different pieces and here it includes {{e 1 A, e… view at source ↗
Figure 3
Figure 3. Figure 3: The representation of a crossing cuts puzzle and its solution, illustrated here for the simplest 2 cuts (and 3 pieces) puzzle. A: Each piece {p1, p2, p3} is represented by its vertices and edges in some arbitrary Euclidean coordinate system (which conveniently may be centered at the center of mass). B: Each mating pairs two edges of two different pieces. In our case it takes just the matings {{e 3 A, e1 B}… view at source ↗
Figure 4
Figure 4. Figure 4: In (generic) crossing cuts puzzles only matings of type 1 are allowed, while configurations of type 2 or 3 are prohibited. In particular, mates must be of equal length and overlap. α1 α2 β1 β2 [PITH_FULL_IMAGE:figures/full_fig_p015_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: The mate angle constraint dictates α1 + β1 = α2 + β2 = π. In the following we will refer to the mating constraints also as predicates, i.e., ∀i ∈ {1, 2} Ci [PITH_FULL_IMAGE:figures/full_fig_p015_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: The effect of noise on edge length. A: Each of the vertices of a piece pi is perturbed inwards along a uniformly distributed direction ]~ j i and as far as a uniformly distributed distance ||~ j i || to create the ε-noisy piece p˜i . B: A case where edge e increases in size after the application of noise, even though all the vertices collapsed inwards to end up as e˜. Clearly, ||e˜|| is bounded by ||e|| … view at source ↗
Figure 7
Figure 7. Figure 7: If the “clean” edge e (in green) stretches (w.l.o.g) from u1 = (0, 0) to u2 = (L, 0), the vertices of the ε-noisy edge must lie in (a subset of) the corresponding error zones. When considering the angle of the ε-noisy edge e˜ (in red), the worst case occurs when one of the vertices (say, u1) is only perturbed horizontally by ε, while the other (say, u2) is perturbed to maximize the rotation, i.e, to a poin… view at source ↗
Figure 8
Figure 8. Figure 8: The effect of noise on the mate angle constraint. A: Without noise, angles must comply to the original constraint α1 + β1 = α2 + β2 = π. B: After applying the noise the ε-noisy angles are affected by the change in orientation in all edges that meet at both vertices of both mates, to result in the bound in the text [PITH_FULL_IMAGE:figures/full_fig_p020_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: Example of a noisy pictorial crossing cut puzzle. A: A noisy pictorial crossing cuts puzzle is an unordered set of pictorial noisy pieces and recall that the noise is geometrical, not pictorial. The four pieces highlighted in purple are those shown in the next panel. B: A closeup on four pictorial neighbors in their original position after they are cut from the original pictorial polygon and then contamina… view at source ↗
Figure 10
Figure 10. Figure 10: The stages of representing a crossing cuts puzzle as a planar graph for the purpose of synthesis. In this selected example, the green quadrilateral is the global puzzle shape S whose boundary is defined by four lines (dashed blue). Three additional lines are defined as the crossing cuts (dashed red) and the intersection points of all these 7 lines that also lie inside or on the border of S are considered … view at source ↗
Figure 11
Figure 11. Figure 11: Two selected synthesized circular puzzles for the analysis of puzzle properties. Shown are the puzzle as a bag of pieces and the corresponding ground truth solution. The numbers of cuts used for these examples are 20 and 100 while the corresponding number of pieces are 63 and 1806, respectively. DB2 - general apictorial puzzles for solvers evaluation: Unlike the specifically crafted puz￾zle shape used for… view at source ↗
Figure 12
Figure 12. Figure 12: One selected synthesized polygonal puzzle (30 cuts, 200 pieces) from DB2.The left column shows the process of generating the random puzzle shape in the work space using the convex hull of random sample points. The middle column illustrates the ground truth solution and the right column shows the puzzles as a bag of pieces as provided to potential solvers. solution for all puzzles, in its published version… view at source ↗
Figure 13
Figure 13. Figure 13: An example of a perturbed grid pictorial puzzles from DB3 (with 8 cuts and 24 pieces), both a a bag of pieces and the corresponding ground truth solution. In addition to the the 3 datasets above, we created two additional datasets for future work by the community DB4 - General pictorial dataset: is another pictorial dataset for future research where the cuts are complete arbitrary and no special care is t… view at source ↗
Figure 14
Figure 14. Figure 14: One selected example of a general pictorial puzzle (with 7 cuts and 18 pieces) from DB4. Note that some small pieces appear only in the ground truth row as the noise removed them completely from the bag of pieces in the puzzle to solve. DB5 - Square piece pictorial dataset: As mentioned in Sec. 3, from a geometrical point of view, strictly square piece puzzles are a very special case of crossing cuts puzz… view at source ↗
Figure 15
Figure 15. Figure 15: Expected cut length and probability of cut intersection.. A: A unit circle cut ci with a central angle Θi can be considered w.l.o.g to be horizontal, leading to an expected length as in the text. B: Two cuts c1 and c2 intersect if and only if the vertices of the second cut (in green) lie in different arcs (in blue and orange) generated by the first cut (in red). the number of cuts, as intersecting cuts co… view at source ↗
Figure 16
Figure 16. Figure 16: Empirical average edge length with growing number of cuts, as evaluated on DB1, compared to the theoretical behavior from Eq. 6. Error bars are ±1 SE. The green line shows the diminishing second order terms of the Taylor approximation. the narrower the distribution becomes. We have therefore measured this property empirically using our synthesized datasets and Fig. 17A reports these findings. Note how in … view at source ↗
Figure 17
Figure 17. Figure 17: Probability density of edge length in crossing cuts puzzles. A: Empirical distribution for growing number of cuts, as evaluated on noisy puzzles from DB1. Note how the distribution gets narrower with the number of crossing cuts, as depicted by a steeper slope in the log scale. Error bars are ±1 SE. B: Empirical edge length distribution with growing number of cuts, as evaluated on DB3. While it is impossib… view at source ↗
Figure 18
Figure 18. Figure 18: The empirical expected number of puzzle pieces with growing number of cuts, compared to the theoretical expected behavior (Eq. 8). Error bars are ±1 SE. 7.8 Expected number of edges per piece As discussed in Sec. 3 , the crossing cuts puzzle model cuts the puzzle shape into convex polygonal pieces. Clearly, these pieces can have different number of edges and there is no a￾priori inherent limit to this num… view at source ↗
Figure 19
Figure 19. Figure 19: Expected ratios of pieces with a particular number of edges as a function of the number of crossing cuts. Note how quadrilaterals are always the majority, followed closely by triangular pieces and the less frequent pentagons. These three classes of polygons quickly converge to account for approximately 95% of all pieces. Note how the ratios converge quickly and remain essentially invariant to the number o… view at source ↗
Figure 20
Figure 20. Figure 20: The average number of geometrically admissible matings for each edge as a function of noise level. Each graph shows the potential number of mates that satisfy both C˜ 1 and C˜ 2, summed over all edges. The rapid growth indicates the harmful effect of noise. Note how the numbers converge to twice the number of edges in the puzzle since each mating is counted twice, one for each of its participating edges. … view at source ↗
Figure 21
Figure 21. Figure 21: The placement of noisy pieces can be ambiguous. When noise is applied to this simple crossing cuts puzzle (A,B), there could be different placements of the noisy pieces that might count as “correct” (C,D). To address these difficulties we approach the problem in stages, and in particular, we begin with the simpler problem of solving the puzzle when the correct matings are given also. More concretely, we f… view at source ↗
Figure 22
Figure 22. Figure 22: The puzzle with given matings is abstracted as a spring-mass system that evolves over time towards convergence state. If the pieces are far apart (left), the springs pull them closer. When then pieces overlap (middle), the springs pull them apart again. With some damping (i.s., loss of energy due to friction), the system eventually converges to a state of minimal energy. In practice there are off-the-shel… view at source ↗
Figure 23
Figure 23. Figure 23: shows several snapshots from this dynamical process. A B C D [PITH_FULL_IMAGE:figures/full_fig_p041_23.png] view at source ↗
Figure 24
Figure 24. Figure 24: 0-loops formation from pairwise matings. A: A bag M˜ of 5 potential matings, of which (e 1 A, e0 E) is wrong but included because it satisfied both C˜ 1 and C˜ 2. B: The loop (e 1 A, e4 B) → (e 3 B, e2 C ) → (e 1 C , e2 D) → (e 1 D, e2 A) is identified and supports the plausibility of its constituent matings. Note that the path ending with (e 1 A, e0 E) does not close a loop because the mating (e 2 E, e2 … view at source ↗
Figure 25
Figure 25. Figure 25: Hierarchical loops formation. Shown left to right, top to bottom, the formation of a higher level loop (in this case, 1-loop) is done by scanning the boundary of the lower-level loop (in this case, 0-loop) until looping all around it with consistent 0-loops that match existing matings and pieces. In particular, the last added 0-loop much also match the first added one. The process just described construct… view at source ↗
Figure 26
Figure 26. Figure 26: The outline of the reconstruction process. A: Hierarchical of all levels are founds.where each level is used as a starting point to search the next level. Notice that the max level loop does not cover the entire puzzle. B: The hierarchical loops are merged by iterating over the loop levels in decreasing order. Each level is merged in increasing order based on the score. C: The merged pieces are positioned… view at source ↗
Figure 27
Figure 27. Figure 27: illustrates a selected result of the pictorial extrapolation and compares it to the original pictorial content. It goes without saying that in our case the available information is taken from the ε-noisy (i.e., “eroded”) piece while the pictorially extrapolated (i.e., “diluted”) piece usually extends even beyond the boundaries of the original noiseless piece. A B C D [PITH_FULL_IMAGE:figures/full_fig_p04… view at source ↗
Figure 28
Figure 28. Figure 28: The pictorial scoring process in action. Two running windows (in green) are simultaneously scanning the extrapolated pictorial content of the two candidate mates (in orange). The sample points are shown in black. The differences in window averages at all corresponding locations are aggregated into a G + 1 dimensional vector, whose L1 norm serves as the dissimilarity measure S(m). Note that the pictorial d… view at source ↗
Figure 29
Figure 29. Figure 29: Being conservative, the performance metric can score a solution low even if intuitively it is good. In this 30 cuts/326 pieces noisy puzzle the reconstructed solution is qualitatively similar to the noiseless ground truth and should be considered a success. And yet, this solution scores just 0.56/1.00 by Eq. 18 because the noise is rather big, the gaps created between the eroded pieces is significant, and… view at source ↗
Figure 30
Figure 30. Figure 30: Qualitative performance of piece positioning for known matings. Since pictorial information plays no role in this test, we omit pictorial examples. A: Initial random placement of pieces. Keep in mind that despite the messy organization the mates (i.e., the springs) are set correctly and we are interested to examine whether such random initial state can lead to undesired local minima. B: Ground truth assem… view at source ↗
Figure 31
Figure 31. Figure 31: Quantitative performance of piece positioning for known matings. The dotted lines show the value of ¯ξ to appreciate how high it can get. A: Average positioning score of the two-phase dynamical system as a function of noise level, computed from 10 random puzzles for selected numbers of crossing cuts/pieces. Shaded bands are ±1 SE. B: Positioning score after the application of the second phase of the dynam… view at source ↗
Figure 32
Figure 32. Figure 32: Examples of successful reconstruction results. A: The unordered bag of puzzle pieces which the solver receives as input. B: The ground truth assembly of (noiseless) pieces C: The reconstruction result of the noisy puzzle. D, E, F: A zoomed area of the noiseless ground truth, the noisy ground truth, and the solution. Unlike in the ground truth, the pieces in the noisy ground truth and in the solution do no… view at source ↗
Figure 33
Figure 33. Figure 33: Reconstruction results on DB2 selected DB2 puzzles. A: Results tested on four subsets from DB2, each including 10 random puzzles, showing the positioning score, the precision, and recall of the matings. The sets used are D1:(a=8, p=26, ξ=1%, ¯ξ=10%), D2:(a=10, p=39, ξ=0.5%, ¯ξ=6%), D3:(a=19, p=131, ξ=0.1%, ¯ξ=2%), D4:(a=35, p=435, ξ=0.01%, ¯ξ=0.4%), where a is number of cuts, p is average number of pieces… view at source ↗
Figure 34
Figure 34. Figure 34: Selected examples of pictorial puzzle solutions from DB3 (A,B - perturbed square jigsaw puzzles) and DB4 (C, D - general crossing cuts puzzles) having various number of cuts, piece size, noise levels, and visual contents. Top row shows the original image/puzzle. Second row represents the puzzle that was submitted to the solver, and the bottom row shows the solution (slightly scaled down to fit the allotte… view at source ↗
Figure 35
Figure 35. Figure 35: Pooled quantitative performance on pictorial puzzles. A: Averaged on 10 puzzles from DB3, applying the pictorial constraints (P) on top of the geometrical ones (G) saves approximately 50% of the matings to test. B: Precision and recall (Eq. 15) and position score (Eq. 18) for the pictorial puzzles from DB3 C: Precision and recall for DB4 puzzles. enough expressive power to allow more real life application… view at source ↗
read the original abstract

Jigsaw puzzle solving, the problem of constructing a coherent whole from a set of non-overlapping unordered visual fragments, is fundamental to numerous applications, and yet most of the literature of the last two decades has focused thus far on less realistic puzzles whose pieces are identical squares. Here, we formalize a new type of jigsaw puzzle where the pieces are general convex polygons generated by cutting through a global polygonal shape with an arbitrary number of straight cuts, a generation model inspired by the celebrated Lazy caterer sequence. We analyze the theoretical properties of such puzzles, including the inherent challenges in solving them once pieces are contaminated with geometrical noise. To cope with such difficulties and obtain tractable solutions, we abstract the problem as a multi-body spring-mass dynamical system endowed with hierarchical loop constraints and a layered reconstruction process. We define evaluation metrics and present experimental results on both apictorial and pictorial puzzles to show that they are solvable completely automatically.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 0 minor

Summary. The paper formalizes a new class of jigsaw puzzles in which convex polygonal pieces are generated by an arbitrary number of straight cuts through a global shape (inspired by the lazy caterer's sequence). It analyzes theoretical properties and noise-induced challenges, then abstracts the assembly task as a multi-body spring-mass dynamical system equipped with hierarchical loop constraints and a layered reconstruction process. Experiments on both apictorial and pictorial instances are presented to demonstrate that the puzzles can be solved completely automatically.

Significance. If the spring-mass formulation with loop constraints reliably recovers the correct global assembly under realistic geometric noise, the work would introduce a practically relevant extension of jigsaw-puzzle research beyond square-piece instances and supply a concrete generation model together with an automatic solver. The explicit treatment of crossing-cut geometry and the definition of evaluation metrics are positive contributions that could support further reproducible studies.

major comments (2)
  1. [Abstract] Abstract: the central claim that the multi-body spring-mass system with hierarchical loop constraints 'solves noisy instances' and yields 'completely automatic' solutions is load-bearing, yet the abstract supplies neither the explicit energy function, the integration scheme, nor any convergence or basin-of-attraction analysis. Without these elements it is impossible to assess whether the method escapes the local minima that the skeptic correctly flags as a risk when vertex positions are perturbed by cutting noise.
  2. [Abstract] Abstract (and the description of the layered reconstruction process): the assumption that the dynamical system converges to the unique correct assembly even after realistic geometric noise is stated without quantitative support (e.g., success rate versus noise variance, number of cuts, or piece count). This omission directly undermines the claim that the approach handles the 'inherent challenges' identified in the theoretical analysis.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the detailed and constructive comments. We address each major comment below, clarifying the manuscript content and indicating revisions where appropriate.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the central claim that the multi-body spring-mass system with hierarchical loop constraints 'solves noisy instances' and yields 'completely automatic' solutions is load-bearing, yet the abstract supplies neither the explicit energy function, the integration scheme, nor any convergence or basin-of-attraction analysis. Without these elements it is impossible to assess whether the method escapes the local minima that the skeptic correctly flags as a risk when vertex positions are perturbed by cutting noise.

    Authors: The abstract is a high-level summary; the explicit energy function, integration scheme (Euler integration with the described forces), and hierarchical loop constraints are fully specified in Section 3. The layered reconstruction process appears in Section 4. No formal basin-of-attraction analysis is provided, but Section 5 reports consistent convergence to the correct assembly across all tested noisy instances. We will revise the abstract to reference the energy formulation and experimental robustness. revision: partial

  2. Referee: [Abstract] Abstract (and the description of the layered reconstruction process): the assumption that the dynamical system converges to the unique correct assembly even after realistic geometric noise is stated without quantitative support (e.g., success rate versus noise variance, number of cuts, or piece count). This omission directly undermines the claim that the approach handles the 'inherent challenges' identified in the theoretical analysis.

    Authors: Section 5 supplies the requested quantitative support: success rates are tabulated versus noise variance, number of cuts, and piece count for both apictorial and pictorial cases, showing complete automatic recovery in all reported trials. The abstract summarizes these outcomes. We will revise the abstract to include a concise statement of the empirical success rates. revision: yes

Circularity Check

0 steps flagged

No significant circularity; modeling choice is independent of claimed results

full rationale

The paper presents an abstraction of the jigsaw problem as a multi-body spring-mass dynamical system with hierarchical loop constraints and layered reconstruction. This is introduced as a modeling decision to obtain tractable solutions, followed by experimental validation on noisy puzzles. No equations, fitted parameters renamed as predictions, or self-citations are shown in the provided text that would reduce the central claim to its own inputs by construction. The derivation chain is self-contained as a forward simulation approach whose success is evaluated externally via defined metrics and experiments, consistent with a non-circular contribution.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

Review performed on abstract only; therefore the ledger records only the modeling choices explicitly named in the abstract.

axioms (1)
  • domain assumption Pieces are convex polygons produced by an arbitrary number of straight cuts through a global polygonal shape
    This generation model is the definitional premise of the new puzzle class.
invented entities (1)
  • multi-body spring-mass dynamical system with hierarchical loop constraints no independent evidence
    purpose: To model automatic reconstruction under geometric noise
    The central abstraction introduced to make the problem tractable

pith-pipeline@v0.9.0 · 5701 in / 1168 out tokens · 27656 ms · 2026-05-24T13:47:56.150011+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

  • IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel echoes
    ?
    echoes

    ECHOES: this paper passage has the same mathematical shape or conceptual pattern as the Recognition theorem, but is not a direct formal dependency.

    we abstract the problem as a multi-body spring-mass dynamical system endowed with hierarchical loop constraints and a layered reconstruction process

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

77 extracted references · 77 canonical work pages · 1 internal anchor

  1. [1]

    A DLURU , N., Y ANG , X., AND LATECKI , L. J. Sequential monte carlo for maximum weight subgraphs with application to solving image jigsaw puzzles. International journal of computer vision 112 , 3 (2015), 319–341

    work page 2015

  2. [2]

    Solving square jigsaw puzzles using dynamic programming and the hungarian procedure

    A LAJLAN , N. Solving square jigsaw puzzles using dynamic programming and the hungarian procedure. American Journal of Applied Sciences 6, 11 (2009), 1941

    work page 2009

  3. [3]

    PSQP: Puzzle solving by quadratic programming

    A NDALO , F., T AUBIN , G., AND GOLDENSTEIN , S. PSQP: Puzzle solving by quadratic programming. IEEE PAMI 39, 2 (2016), 385–396

    work page 2016

  4. [4]

    A., C ARNEIRO , G., T AUBIN , G., G OLDENSTEIN , S., AND VELHO , L

    A NDALÓ , F. A., C ARNEIRO , G., T AUBIN , G., G OLDENSTEIN , S., AND VELHO , L. Automatic reconstruction of ancient portuguese tile panels. IEEE Comput. Graphics Appl (2016)

    work page 2016

  5. [5]

    Probability models in engineering and science

    B ENAROYA , H., AND HAN, S. Probability models in engineering and science

    work page

  6. [6]

    Hot tiles: A heat diffusion based descriptor for automatic tile panel assembly

    B RANDÃO , S., AND MARQUES , M. Hot tiles: A heat diffusion based descriptor for automatic tile panel assembly. In European Conference on Computer Vision (2016), Springer, pp. 768–782

    work page 2016

  7. [7]

    J., L AKEN , L., D UTRÉ , P., G OOL , L., R USINKIEWICZ , S., AND WEYRICH , T

    B ROWN , B. J., L AKEN , L., D UTRÉ , P., G OOL , L., R USINKIEWICZ , S., AND WEYRICH , T. Tools for virtual reassembly of fresco fragments. International Journal of Heritage in the Digital Era 1 (2012), 313–329

    work page 2012

  8. [8]

    Jigsaw puzzle solving using approximate string matching and best-first search

    B UNKE , H., AND KAUFMANN , G. Jigsaw puzzle solving using approximate string matching and best-first search. In International Conference on Computer Analysis of Images and Patterns (1993), Springer, pp. 299–308

    work page 1993

  9. [9]

    B URDEA , B., AND WOLFSON , H. J. Solving jigsaw puzzles by a robot. IEEE Transactions on robotics and automation 5, 6 (1989), 752–764

    work page 1989

  10. [10]

    J., R USINKIEWICZ , S., F UNKHOUSER , T., AND WEYRICH , T

    C ASTAÑEDA , A., B ROWN , B. J., R USINKIEWICZ , S., F UNKHOUSER , T., AND WEYRICH , T. Global consistency in the automatic assembly of fragmented artefacts. In VAST (2011). 60

    work page 2011

  11. [11]

    C ATTO, E. Box2d. https://github.com/erincatto/Box2D

    work page

  12. [12]

    S., A VIDAN , S., AND FREEMAN , W

    C HO, T. S., A VIDAN , S., AND FREEMAN , W. T. A probabilistic image jigsaw puzzle solver. In 2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (2010), IEEE, pp. 183–190

    work page 2010

  13. [13]

    G., F LECK , M

    C HUNG , M. G., F LECK , M. M., AND FORSYTH , D. A. Jigsaw puzzle solver using shape and color. In ICSP’98. 1998 Fourth International Conference on Signal Processing (Cat. No. 98TH8344) (1998), vol. 2, IEEE, pp. 877–880

    work page 1998

  14. [14]

    Region filling and object removal by exemplar-based image inpainting

    C RIMINISI , A., P ÉREZ , P., AND TOYAMA, K. Region filling and object removal by exemplar-based image inpainting. IEEE Transactions on image processing 13, 9 (2004), 1200–1212

    work page 2004

  15. [15]

    Constructing the topological solution of jigsaw puzzles

    D E BOCK , J., D E SMET, R., P HILIPS , W., AND D’H AEYER , J. Constructing the topological solution of jigsaw puzzles. In 2004 International Conference on Image Processing, 2004. ICIP’04. (2004), vol. 3, IEEE, pp. 2127–2130

    work page 2004

  16. [16]

    D., AND DEMAINE , M

    D EMAINE , E. D., AND DEMAINE , M. L. Jigsaw puzzles, edge matching, and polyomino packing: Connections and complexity. Graphs and Combinatorics 23, 1 (Jun 2007), 195–208

    work page 2007

  17. [17]

    Solving archaeological puzzles

    D ERECH , N., T AL, A., AND SHIMSHONI , I. Solving archaeological puzzles. Pattern Recognition (2021), 108065

    work page 2021

  18. [18]

    D ICE , L. R. Measures of the amount of ecologic association between species. Ecology 26, 3 (1945), 297–302

    work page 1945

  19. [19]

    An image processing approach for jigsaw puzzle assembly

    F EI, N., Z HUANG , F., R ENQIANG , L., Q IXIN , C., AND YANZHENG , Z. An image processing approach for jigsaw puzzle assembly. Assembly Automation 27, 1 (2007), 25–30

    work page 2007

  20. [20]

    Apictorial jigsaw puzzles: The computer solution of a problem in pattern recognition

    F REEMAN , H., AND GARDER , L. Apictorial jigsaw puzzles: The computer solution of a problem in pattern recognition. IEEE Transactions on Electronic Computers, 2 (1964), 118–127

    work page 1964

  21. [21]

    J., D OBKIN , D., R USINKIEWICZ , S., AND WEYRICH , T

    F UNKHOUSER , T., S HIN , H., T OLER -FRANKLIN , C., C ASTAÑEDA , A., B ROWN , B. J., D OBKIN , D., R USINKIEWICZ , S., AND WEYRICH , T. Learning how to match fresco fragments. ACM Journal on Computing and Cultural Heritage 4 (2011), 7:1–7:13

    work page 2011

  22. [22]

    G ALLAGHER , A. C. Jigsaw puzzles with pieces of unknown orientation. In 2012 IEEE Conference on Computer Vision and Pattern Recognition (2012), IEEE, pp. 382–389

    work page 2012

  23. [23]

    jigsaw puzzle

    G ASSNER , N., B AASE , W., AND MATTHEWS , B. A test of the "jigsaw puzzle" model for protein folding by multiple methionine substitutions within the core of t4 lysozyme. Proceedings of the National Academy of Sciences 93 , 22 (1996), 12155–12158

    work page 1996

  24. [24]

    ‘The more things change’: HUMINT in the cyber age

    G IOE , D. ‘The more things change’: HUMINT in the cyber age. In The Palgrave handbook of security, risk and intelligence. Springer, 2017, pp. 213–227

    work page 2017

  25. [25]

    A global approach to automatic solution of jigsaw puzzles

    G OLDBERG , D., M ALON , C., AND BERN , M. A global approach to automatic solution of jigsaw puzzles. In Proceedings of the eighteenth annual symposium on Computational geometry (2002), ACM, pp. 82–87

    work page 2002

  26. [26]

    Reaching the point of no return: the computational revolution in archaeology

    G ROSMAN , L. Reaching the point of no return: the computational revolution in archaeology. Annual review of Anthropology 45 (2016), 129–145

    work page 2016

  27. [27]

    From square pieces to brick walls: The next challenge in solving jigsaw puzzles

    G UR, S., AND BEN-S HAHAR , O. From square pieces to brick walls: The next challenge in solving jigsaw puzzles. In Proceedings of the IEEE International Conference on Computer Vision (2017), pp. 4029–4037

    work page 2017

  28. [28]

    Reassembling fractured objects by geometric matching

    H UANG , Q., F LÖRY, S., G ELFAND , N., H OFER , M., AND POTTMANN , H. Reassembling fractured objects by geometric matching. ACM Trans. Graph. 25 (2006), 569–578

    work page 2006

  29. [29]

    An optimal algorithm for extracting the regions of a plane graph

    J IANG , X., AND BUNKE , H. An optimal algorithm for extracting the regions of a plane graph. Pattern Recognition Letters 14, 7 (1993), 553–558

    work page 1993

  30. [30]

    Scientific puzzle solving: Current techniques and applications

    K LEBER , F., AND SABLATNIG , R. Scientific puzzle solving: Current techniques and applications. In CAA (2009)

    work page 2009

  31. [31]

    A survey of techniques for document and archaeology artefact reconstruction

    K LEBER , F., AND SABLATNIG , R. A survey of techniques for document and archaeology artefact reconstruction. In ICDAR (2009), pp. 1061–1065. 61

    work page 2009

  32. [32]

    Computer-aided reconstruction and new matches in the forma urbis romae

    K OLLER , D., AND LEVOY, M. Computer-aided reconstruction and new matches in the forma urbis romae. Bullettino Della Commissione Archeologica Comunale di Roma 2 (2006), 103–125

    work page 2006

  33. [33]

    K ONG , W., AND KIMIA , B. B. On solving 2d and 3d puzzles using curve matching. In Proceedings of the 2001 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. CVPR 2001 (2001), vol. 2, IEEE, pp. II–II

    work page 2001

  34. [34]

    A., D EVAUX, P

    K OSIBA , D. A., D EVAUX, P. M., B ALASUBRAMANIAN , S., G ANDHI , T. L., AND KASTURI , K. An automatic jigsaw puzzle solver. In Proceedings of 12th International Conference on Pattern Recognition (1994), vol. 1, IEEE, pp. 616–618

    work page 1994

  35. [35]

    Jigsawnet: Shredded image reassembly using convolutional neural network and loop-based composition

    L E, C., AND LI, X. Jigsawnet: Shredded image reassembly using convolutional neural network and loop-based composition. IEEE Transactions on Image Processing (2019)

    work page 2019

  36. [36]

    Pairwise matching for 3d fragment reassembly based on boundary curves and concave- convex patches

    L I, Q., G ENG , G., AND ZHOU , M. Pairwise matching for 3d fragment reassembly based on boundary curves and concave- convex patches. IEEE Access 8 (2020), 6153–6161

    work page 2020

  37. [37]

    The geological development of the arctic

    L INDSTRÖM , M. The geological development of the arctic. In The Arctic. Routledge, 2019, pp. 3–25

    work page 2019

  38. [38]

    Automated assembly of shredded pieces from multiple photos

    L IU, H., C AO, S., AND YAN, S. Automated assembly of shredded pieces from multiple photos. IEEE Transactions on Multimedia 13, 5 (2011), 1154–1162

    work page 2011

  39. [39]

    A new technique for solving a jigsaw puzzle

    M AKRIDIS , M., AND PAPAMARKOS , N. A new technique for solving a jigsaw puzzle. In 2006 International Conference on Image Processing (2006), IEEE, pp. 2001–2004

    work page 2006

  40. [40]

    Mitochondrial dna as a genomic jigsaw puzzle

    M ARANDE , W., AND BURGER , G. Mitochondrial dna as a genomic jigsaw puzzle. Science 318, 5849 (2007), 415–415

    work page 2007

  41. [41]

    Fractured object reassembly via robust surface registration

    M AVRIDIS , P., A NDREADIS , A., AND PAPAIOANNOU , G. Fractured object reassembly via robust surface registration. In Eurographics (2015)

    work page 2015

  42. [42]

    Semi-automatic geometry-driven reassembly of fractured archeological objects

    M ELLADO , N., R EUTER , P., AND SCHLICK , C. Semi-automatic geometry-driven reassembly of fractured archeological objects. In VAST (2010)

    work page 2010

  43. [43]

    Robust solvers for square jigsaw puzzles

    M ONDAL , D., WANG , Y., AND DUROCHER , S. Robust solvers for square jigsaw puzzles. In 2013 International Conference on Computer and Robot Vision (2013), IEEE, pp. 249–256

    work page 2013

  44. [44]

    M OORE , T. L. Using euler’s formula to solve plane separation problems. The College Mathematics Journal 22 , 2 (1991), 125–130

    work page 1991

  45. [45]

    Assembly of puzzles by connecting between blocks

    M URAKAMI , T., T OYAMA, F., S HOJI , K., AND MIYAMICHI , J. Assembly of puzzles by connecting between blocks. In 2008 19th International Conference on Pattern Recognition (2008), IEEE, pp. 1–4

    work page 2008

  46. [46]

    R., D REWSEN , P., AND HANSEN , K

    N IELSEN , T. R., D REWSEN , P., AND HANSEN , K. Solving jigsaw puzzles using image features. Pattern Recognition Letters 29, 14 (2008), 1924–1933

    work page 2008

  47. [47]

    Reassembling thin artifacts of unknown geometry

    O XHOLM , G., AND NISHINO , K. Reassembling thin artifacts of unknown geometry. In VAST (2011)

    work page 2011

  48. [48]

    Solving multiple square jigsaw puzzles with missing pieces

    P AIKIN , G., AND TAL, A. Solving multiple square jigsaw puzzles with missing pieces. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (2015), pp. 4832–4839

    work page 2015

  49. [49]

    A computer-assisted constraint-based system for assembling fragmented objects

    P ALMAS , G., P IETRONI , N., C IGNONI , P., AND SCOPIGNO , R. A computer-assisted constraint-based system for assembling fragmented objects. 2013 Digital Heritage International Congress (DigitalHeritage) 1 (2013), 529–536

    work page 2013

  50. [50]

    On the automatic assemblage of arbitrary broken solid artefacts

    P APAIOANNOU , G., AND KARABASSI , E.-A. On the automatic assemblage of arbitrary broken solid artefacts. Image Vis. Comput. 21 (2003), 401–412

    work page 2003

  51. [51]

    Virtual archaeologist: Assembling the past

    P APAIOANNOU , G., K ARABASSI , E.-A., AND THEOHARIS , T. Virtual archaeologist: Assembling the past. IEEE Computer Graphics and Applications 21 (2001), 53–59

    work page 2001

  52. [52]

    Contour-shape based reconstruction of fragmented, 1600 bc wall paintings

    P APAODYSSEUS , C., P ANAGOPOULOS , T., E XARHOS , M., T RIANTAFILLOU , C., F RAGOULIS , D., AND DOUMAS , C. Contour-shape based reconstruction of fragmented, 1600 bc wall paintings. IEEE Trans. Signal Process. 50 (2002), 1277– 1288. 62

    work page 2002

  53. [53]

    Deepzzle: Solving visual jigsaw puzzles with deep learning and shortest path optimization

    P AUMARD , M.-M., P ICARD , D., AND TABIA , H. Deepzzle: Solving visual jigsaw puzzles with deep learning and shortest path optimization. IEEE Transactions on Image Processing 29 (2020), 3569–3581

    work page 2020

  54. [54]

    P INTUS , R., P AL, K., Y ANG , Y., W EYRICH , T., G OBBETTI , E., AND RUSHMEIER , H. E. Geometric analysis in cultural heritage. In GCH (2014), pp. 117–133

    work page 2014

  55. [55]

    A fully automated greedy square jigsaw puzzle solver

    P OMERANZ , D., S HEMESH , M., AND BEN-S HAHAR , O. A fully automated greedy square jigsaw puzzle solver. In CVPR 2011 (2011), IEEE, pp. 9–16

    work page 2011

  56. [56]

    M., AND BADLER , N

    R ADACK , G. M., AND BADLER , N. I. Jigsaw puzzle matching using a boundary-centered polar encoding. Computer Graphics and Image Processing 19, 1 (1982), 1–17

    work page 1982

  57. [57]

    O., AND NETANYAHU , N

    R IKA , D., S HOLOMON , D., D AVID, E. O., AND NETANYAHU , N. S. A novel hybrid scheme using genetic algorithms and deep learning for the reconstruction of portuguese tile panels. In Proceedings of the Genetic and Evolutionary Computation Conference (2019), ACM, pp. 1319–1327

    work page 2019

  58. [58]

    ¸ S.,AND ERÇIL , A

    S A ˘GIRO ˘GLU , M. ¸ S.,AND ERÇIL , A. Optimization for automated assembly of puzzles. Top 18, 2 (2010), 321–338

    work page 2010

  59. [59]

    Analyzing and simulating fracture patterns of theran wall paintings

    S HIN , H., D OUMAS , C., F UNKHOUSER , T., R USINKIEWICZ , S., S TEIGLITZ , K., V LACHOPOULOS , A., AND WEYRICH , T. Analyzing and simulating fracture patterns of theran wall paintings. Journal on Computing and Cultural Heritage (JOCCH) 5, 3 (2012), 10

    work page 2012

  60. [60]

    S HOLOMON , D., D AVID, O., AND NETANYAHU , N. S. A genetic algorithm-based solver for very large jigsaw puzzles. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (2013), pp. 1767–1774

    work page 2013

  61. [61]

    E., AND NETANYAHU , N

    S HOLOMON , D., D AVID, O. E., AND NETANYAHU , N. S. A generalized genetic algorithm-based solver for very large jigsaw puzzles of complex types. In Twenty-Eighth AAAI Conference on Artificial Intelligence (2014)

    work page 2014

  62. [62]

    S ON, K., H AYS, J., AND COOPER , D. B. Solving square jigsaw puzzles with loop constraints. In European Conference on Computer Vision (2014), Springer, pp. 32–46

    work page 2014

  63. [63]

    S ON, K., H AYS, J., AND COOPER , D. B. Solving square jigsaw puzzle by hierarchical loop constraints. IEEE transactions on pattern analysis and machine intelligence (2018)

    work page 2018

  64. [64]

    B., ET AL

    S ON, K., H AYS, J., C OOPER , D. B., ET AL . Solving small-piece jigsaw puzzles by growing consensus. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (2016), pp. 1193–1201

    work page 2016

  65. [65]

    Least-squares rigid motion using svd

    S ORKINE -H ORNUNG , O., AND RABINOVICH , M. Least-squares rigid motion using svd. Computing 1, 1 (2017)

    work page 2017

  66. [66]

    J., W EYRICH , T., FUNKHOUSER , T., AND RUSINKIEWICZ , S

    T OLER -FRANKLIN , C., B ROWN , B. J., W EYRICH , T., FUNKHOUSER , T., AND RUSINKIEWICZ , S. Multi-feature matching of fresco fragments. In SIGGRAPH 2010 (2010)

    work page 2010

  67. [67]

    Assembly of puzzles using a genetic algorithm

    T OYAMA, F., F UJIKI , Y., S HOJI , K., AND MIYAMICHI , J. Assembly of puzzles using a genetic algorithm. In Object recognition supported by user interaction for service robots (2002), vol. 4, IEEE, pp. 389–392

    work page 2002

  68. [68]

    Automatic color based reassembly of fragmented images and paintings

    T SAMOURA , E., AND PITAS, I. Automatic color based reassembly of fragmented images and paintings. IEEE Transactions on Image Processing 19, 3 (2009), 680–690

    work page 2009

  69. [69]

    The puzzle assembled: Ediacaran guide fossil Cloudina reveals an old proto-Gondwana seaway

    W ARREN , L., Q UAGLIO , F., R ICCOMINI , C., S IMÕES , M., P OIRÉ , D., S TRIKIS , N., A NELLI , L., AND STRIKIS , P. The puzzle assembled: Ediacaran guide fossil Cloudina reveals an old proto-Gondwana seaway. Geology 42 , 5 (05 2014), 391–394

    work page 2014

  70. [70]

    W., L AFOLLETTE , P

    W EBSTER , R. W., L AFOLLETTE , P. S., AND STAFFORD , R. L. Isthmus critical points for solving jigsaw puzzles in computer vision. IEEE transactions on systems, man, and cybernetics 21 , 5 (1991), 1271–1278

    work page 1991

  71. [71]

    Computational reconstruction of ancient artifacts

    W ILLIS , A., AND COOPER , D. Computational reconstruction of ancient artifacts. IEEE Signal Processing Magazine 25 (2008). 63

    work page 2008

  72. [72]

    Solving jigsaw puzzles by computer

    W OLFSON , H., S CHONBERG , E., K ALVIN , A., AND LAMDAN , Y. Solving jigsaw puzzles by computer. Annals of Operations Research 12, 1 (1988), 51–64

    work page 1988

  73. [73]

    Y ANG , X., A DLURU , N., AND LATECKI , L. J. Particle filter with state permutations for solving image jigsaw puzzles. In CVPR 2011 (2011), IEEE, pp. 2873–2880

    work page 2011

  74. [74]

    A shape and image merging technique to solve jigsaw puzzles

    Y AO, F.-H., AND SHAO, G.-F. A shape and image merging technique to solve jigsaw puzzles. Pattern Recognition Letters 24, 12 (2003), 1819–1835

    work page 2003

  75. [75]

    Solving Jigsaw Puzzles with Linear Programming

    Y U, R., R USSELL , C., AND AGAPITO , L. Solving jigsaw puzzles with linear programming. arXiv preprint arXiv:1511.04472 (2015)

    work page internal anchor Pith review Pith/arXiv arXiv 2015

  76. [76]

    A graph-based optimization algorithm for fragmented image reassembly

    Z HANG , K., AND LI, X. A graph-based optimization algorithm for fragmented image reassembly. Graphical Models 76, 5 (2014), 484–495

    work page 2014

  77. [77]

    A puzzle solver and its application in speech descrambling

    Z HAO, Y.-X., S U, M.-C., C HOU , Z.-L., AND LEE, J. A puzzle solver and its application in speech descrambling. In WSEAS International Conference on Computer Engineering and Applications (2007), pp. 171–176

    work page 2007