An \(O(n \log n)\)-algorithm for finding a domino tiling of a plane picture whose number of holes is bounded.
From MaRDI portal
Publication:1401372
DOI10.1016/S0304-3975(02)00497-8zbMath1053.68068OpenAlexW2000775444MaRDI QIDQ1401372
Publication date: 17 August 2003
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0304-3975(02)00497-8
Nonnumerical algorithms (68W05) Computing methodologies for image processing (68U10) Combinatorics in computer science (68R05) Tilings in (2) dimensions (aspects of discrete geometry) (52C20)
Related Items (4)
Fast domino tileability ⋮ Domino tilings and related models: Space of configurations of domains with holes ⋮ A heuristic approach to domino grid problem ⋮ Optimal Partial Tiling of Manhattan Polyominoes
Cites Work
- 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 pictures of the plane with dominoes
- Tiling of planar figures without gaps by dominos: graphical foundations of Thurston if algorithm, parallelization uniqueness and decomposion
- Perfect matchings of polyomino graphs
- Conway's Tiling Groups
This page was built for publication: An \(O(n \log n)\)-algorithm for finding a domino tiling of a plane picture whose number of holes is bounded.
