Published September 2016
| Submitted
Journal Article
Open
Fast Domino Tileability
- Creators
- Pak, Igor
-
Sheffer, Adam
- Tassy, Martin
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.
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.Attached Files
Submitted - 1507.00770v1.pdf
Files
1507.00770v1.pdf
Files
(551.2 kB)
| Name | Size | Download all |
|---|---|---|
|
md5:206b631654e184d69a93ac42355e4672
|
551.2 kB | Preview Download |
Additional details
- Eprint ID
- 70236
- Resolver ID
- CaltechAUTHORS:20160909-101454051
- NSF
- Created
-
2016-09-09Created from EPrint's datestamp field
- Updated
-
2021-11-11Created from EPrint's last_modified field