2
$\begingroup$

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?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
1
$\begingroup$

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).

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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 $\endgroup$
    – Anh Tran
    Dec 14, 2020 at 0:45
  • 1
    $\begingroup$ "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. $\endgroup$
    – Joseph O'Rourke
    Dec 14, 2020 at 0:51
1
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.