# How to solve tiling problem with dancing links?

My end goal is to create an application where the user can load in a 3D mesh and then define a box. The app then try to fit as much mesh as possible into that box.

I figure that would be a pretty difficult problem, so I start small first. Let's say I have an arbitrary simple polygons with arbitrary orientation, how would I figure out how many polygons (and of course, how) I can fit within a bounded boundary (a rectangle for example)?

I dig around and the answer always point down to the Dancing Links algorithm that people used to solve Sudoku. But I fail to understand what is the link between that algorithm and the problem I'm trying to solve. Can someone give me a more verbose answer?

OP. Let's say I have an arbitrary simple polygons with arbitrary orientation, how would I figure out how many polygons (and of course, how) I can fit within a bounded boundary (a rectangle for example)?

I wonder if you are perhaps seeking to reproduce the Conway criteria?

One of the best sources on this topic is this (relatively) recent result, for they take pains to explain the Conway criteria:

Langerman, Stefan, and Andrew Winslow. "A quasilinear-time algorithm for tiling the plane isohedrally with a polyomino." arXiv:1507.02762 (2015).

• Interesting, I will definitely have a look. I wonder if for each tile, we allow arbitrary rotation, how much more complex this problem would be Dec 14, 2020 at 0:45
• "Any prototile satisfying Conway's criterion admits a periodic tiling of the plane—and does so using only translation and 180-degree rotations." So: not arbitrary rotations. Dec 14, 2020 at 0:51

The following recent paper shows that many problems involving packing geometric objects in the plane are $$\exists\mathbb{R}$$-complete:

Mikkel Abrahamsen, Tillmann Miltzow and Nadja Seiferth, Framework for $$\exists\mathbb{R}$$-Completeness of Two-Dimensional Packing Problems, https://arxiv.org/abs/2004.07558