All Questions
Tagged with tiling computational-complexity
8 questions
2
votes
1
answer
158
views
On sets of rectangles that can all together form at least one big rectangle
Let us say a set of $n$ rectangles is rectifiable if all $n$ rectangles together form a big rectangle without gaps or overlaps.
Question: How hard computationally is the question of deciding whether a ...
- 5,979
19
votes
1
answer
616
views
How hard is it to tell when a finite set tiles the integers?
Given a nonempty set $B$ of integers between 1 and $n$, we wish to determine whether or not $\mathbb{Z}$ can be tiled with translates of $B$ (that is, covered by disjoint translates of $B$). I know an ...
- 19.7k
7
votes
1
answer
186
views
Decidability of convex rearrangements of polygons
Triggered by the MO question,
"How many convex shapes can be made with the pieces of the Stomachion?," I would like to pose this question:
Q. Given $n$ polygons in a set $S$, say each with integer ...
- 151k
1
vote
0
answers
43
views
Reference requests for tiling easiness [closed]
For Wang tile problem, is there some general statements in a paper stating that the more tiles (supposed provided by random) available, the easier it is for these tiles to tile the plane? Thank you.
- 867
5
votes
0
answers
145
views
Complexity of $\mathbb{Z}^n$ tilings
Let $\mathcal{T} \subset \mathbb{Z}^n$ be a finite set. Let $\Lambda \subset \mathbb{Z}^n$ be a full rank lattice.
We say that $\mathcal{T}$ is a $\Lambda$-tile for $\mathbb{Z}^n$ if the following ...
- 800
4
votes
1
answer
549
views
Tiling with restricted overlap
Non-overlapping tilings of regions is a well-studied topic.
I wonder if the following variant has been considered:
A tile can be partitioned into several regions, where such regions from different ...
- 15.8k
20
votes
2
answers
2k
views
"a shape that ... lies halfway between a square and a circle"
An article in the
Notices of the AMS, Volume 61, Issue 10, 2014
(PDF download link),
on Khot's Unique Games Conjecture, says this:
Another group ... found a
shape that in a certain sense lies ...
- 151k
5
votes
1
answer
213
views
Aperiodic set of corner Wang Tile [closed]
There is quite some reference on aperiodicity of the edge-type of Wang Tile. But I could not yet find aperiodic corner type of Wang Tiles... Could someone provide me some instances (better with ...
- 867