Fast domino tileability

DOI10.1007/S00454-016-9807-1zbMATH Open1350.68267arXiv1507.00770OpenAlexW2191088981MaRDI QIDQ312152FDOQ312152

Authors: Igor Pak, Adam Sheffer, Martin Tassy 

Publication date: 14 September 2016

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1507.00770

Recommendations

• An \(O(n \log 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

zbMATH Keywords

domino tilingheight functionlozenge tilingtileability

Mathematics Subject Classification ID

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)

Cites Work

• Title not available (Why is that?)
• Markov chain algorithms for planar lattice structures
• Conway's Tiling Groups
• Matching theory
• The Complexity of Enumeration and Reliability Problems
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Sublinear time algorithms
• Title not available (Why is that?)
• Lectures on Dimers
• Tiling with polyominoes
• The undecidability of the domino problem
• Hard tiling problems with simple tiles
• Tiling with polyominoes and combinatorial group theory
• Optimal Point Location in a Monotone Subdivision
• 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.
• Spaces of domino tilings
• Tiling simply connected regions with rectangles
• Tiling a polygon with two kinds of rectangles
• The planar dimer model boundary: A survey
• Shortest paths in planar graphs with real lengths in \(O(n \log^{2} n/ \log \log n)\) time
• The complexity of generalized domino tilings
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Flow in Planar Graphs with Multiple Sources and Sinks
• A characterization of flip-accessibility for rhombus tilings of the whole plane

Cited In (6)

• Kirszbraun-type theorems for graphs
• Tiling with Squares and Packing Dominos in Polynomial Time
• Mixing properties of colourings of the ℤ^d lattice
• Computational complexity of counting coincidences
• Asymptotics for the number of standard tableaux of skew shape and for weighted lozenge tilings
• A variational principle for a non-integrable model

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)