CaltechAUTHORS
  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. https://resolver.caltech.edu/CaltechAUTHORS:20160909-101454051

[img] PDF - Submitted Version
See Usage Policy.

551kB

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20160909-101454051

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.


Item Type:Article
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.1007/s00454-016-9807-1DOIArticle
http://link.springer.com/article/10.1007%2Fs00454-016-9807-1PublisherArticle
https://arxiv.org/abs/1507.00770arXivDiscussion Paper
http://rdcu.be/ts4KPublisherFree ReadCube access
ORCID:
AuthorORCID
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.
Funders:
Funding AgencyGrant Number
NSFUNSPECIFIED
Subject Keywords:Tileability; Height function; Domino tiling; Lozenge tiling
Issue or Number:2
DOI:10.1007/s00454-016-9807-1
Record Number:CaltechAUTHORS:20160909-101454051
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20160909-101454051
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
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:09 Sep 2016 17:21
Last Modified:11 Nov 2021 04:26

Repository Staff Only: item control page