A Caltech Library Service

Fast Domino Tileability

Pak, Igor and Sheffer, Adam and Tassy, Martin (2016) Fast Domino Tileability. Discrete and Computational Geometry, 56 (2). pp. 377-394. ISSN 0179-5376. doi:10.1007/s00454-016-9807-1.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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.

Item Type:Article
Related URLs:
URLURL TypeDescription Paper ReadCube access
Sheffer, Adam0000-0003-3418-5122
Additional Information:© 2016 Springer Science+Business Media New York. Received: 14 July 2015; Revised: 06 April 2016; Accepted: 28 June 2016; First Online: 15 July 2016. We are very grateful to Scott Garrabrant and Yahav Nussbaum for interesting discussions and helpful remarks. The first author was partially supported by the NSF.
Funding AgencyGrant Number
Subject Keywords:Tileability; Height function; Domino tiling; Lozenge tiling
Issue or Number:2
Record Number:CaltechAUTHORS:20160909-101454051
Persistent URL:
Official Citation:Pak, I., Sheffer, A. & Tassy, M. Discrete Comput Geom (2016) 56: 377. doi:10.1007/s00454-016-9807-1
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:70236
Deposited By: Tony Diaz
Deposited On:09 Sep 2016 17:21
Last Modified:11 Nov 2021 04:26

Repository Staff Only: item control page