Fast domino tileability
From MaRDI portal
Publication:312152
DOI10.1007/s00454-016-9807-1zbMath1350.68267arXiv1507.00770OpenAlexW2191088981MaRDI QIDQ312152
Martin Tassy, Adam Sheffer, Igor Pak
Publication date: 14 September 2016
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1507.00770
Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Tilings in (2) dimensions (aspects of discrete geometry) (52C20)
Related Items
Asymptotics for the number of standard tableaux of skew shape and for weighted lozenge tilings, Tiling with Squares and Packing Dominos in Polynomial Time, Kirszbraun-type theorems for graphs, Mixing properties of colourings of the ℤd lattice, A variational principle for a non-integrable model
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The complexity of generalized domino tilings
- A characterization of flip-accessibility for rhombus tilings of the whole plane
- Domino tilings on orientable surfaces
- Tiling groups: New applications in the triangular lattice
- Tiling figures of the plane with two bars
- Domino tiling in planar graphs with regular and bipartite dual. (Pavage par des dominos dans des graphes planaires de dual régulier et biparti)
- Tiling of planar figures without gaps by dominos: graphical foundations of Thurston if algorithm, parallelization uniqueness and decomposion
- Tile invariants: New horizons.
- An \(O(n \log n)\)-algorithm for finding a domino tiling of a plane picture whose number of holes is bounded.
- Tiling with polyominoes and combinatorial group theory
- Spaces of domino tilings
- Tiling simply connected regions with rectangles
- Tiling a polygon with two kinds of rectangles
- Markov Chain Algorithms for Planar Lattice Structures
- Conway's Tiling Groups
- Sublinear Time Algorithms
- Lectures on Dimers
- Shortest Paths in Planar Graphs with Real Lengths in O(nlog2 n/loglogn) Time
- Optimal Point Location in a Monotone Subdivision
- The Complexity of Enumeration and Reliability Problems
- Flow in Planar Graphs with Multiple Sources and Sinks
- Tiling with polyominoes
- The undecidability of the domino problem
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- Hard tiling problems with simple tiles
