Abstract: Domino tileability is a classical problem in Discrete Geometry, famously solved by Thurston for simply connected regions in nearly linear time in the area. In this paper, we improve upon Thurston's height function approach to a nearly linear time in the perimeter.
Recommendations
- An O(n n)-algorithm for finding a domino tiling of a plane picture whose number of holes is bounded.
- Tiling pictures of the plane with dominoes
- On the tileability of polygons with colored dominoes
- The complexity of generalized domino tilings
- Tiling of planar figures without gaps by dominos: graphical foundations of Thurston if algorithm, parallelization uniqueness and decomposion
Cites work
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1256699 (Why is no real title available?)
- scientific article; zbMATH DE number 1741011 (Why is no real title available?)
- scientific article; zbMATH DE number 1048047 (Why is no real title available?)
- scientific article; zbMATH DE number 1792102 (Why is no real title available?)
- scientific article; zbMATH DE number 2125075 (Why is no real title available?)
- A characterization of flip-accessibility for rhombus tilings of the whole plane
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- An \(O(n \log n)\)-algorithm for finding a domino tiling of a plane picture whose number of holes is bounded.
- Conway's Tiling Groups
- Domino tiling in planar graphs with regular and bipartite dual. (Pavage par des dominos dans des graphes planaires de dual régulier et biparti)
- Domino tilings on orientable surfaces
- Flow in Planar Graphs with Multiple Sources and Sinks
- Hard tiling problems with simple tiles
- Lectures on Dimers
- Markov chain algorithms for planar lattice structures
- Matching theory
- Optimal Point Location in a Monotone Subdivision
- Shortest paths in planar graphs with real lengths in \(O(n \log^{2} n/ \log \log n)\) time
- Spaces of domino tilings
- Sublinear time algorithms
- The Complexity of Enumeration and Reliability Problems
- The complexity of generalized domino tilings
- The planar dimer model boundary: A survey
- The undecidability of the domino problem
- Tile invariants: New horizons.
- Tiling a polygon with two kinds of rectangles
- Tiling figures of the plane with two bars
- Tiling groups: New applications in the triangular lattice
- Tiling of planar figures without gaps by dominos: graphical foundations of Thurston if algorithm, parallelization uniqueness and decomposion
- Tiling simply connected regions with rectangles
- Tiling with polyominoes
- Tiling with polyominoes and combinatorial group theory
Cited in
(6)- Tiling with Squares and Packing Dominos in Polynomial Time
- A variational principle for a non-integrable model
- Mixing properties of colourings of the ℤd lattice
- Computational complexity of counting coincidences
- Kirszbraun-type theorems for graphs
- Asymptotics for the number of standard tableaux of skew shape and for weighted lozenge tilings
This page was built for publication: Fast domino tileability
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q312152)
