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]](https://authors.library.caltech.edu/style/images/fileicons/application_pdf.png) |
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: |
| |||||||||||||||
| ORCID: |
| |||||||||||||||
| 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: |
| |||||||||||||||
| 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
