Fast Domino Tileability

作者：Pak Igor^*; Sheffer Adam; Tassy Martin

来源：Discrete & Computational Geometry, 2016, 56(2): 377-394.

DOI：10.1007/s00454-016-9807-1

• Tileability
• Height function
• Domino tiling
• Lozenge tiling

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.

• 出版日期2016-9