Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2016.50
URN: urn:nbn:de:0030-drops-59423
URL: https://drops.dagstuhl.de/opus/volltexte/2016/5942/
Langerman, Stefan ; Winslow, Andrew
A Quasilinear-Time Algorithm for Tiling the Plane Isohedrally with a Polyomino
| pdf-format: |
|
Abstract
A plane tiling consisting of congruent copies of a shape is isohedral provided that for any pair of copies, there exists a symmetry of the tiling mapping one copy to the other. We give a O(n*log^2(n))-time algorithm for deciding if a polyomino with n edges can tile the plane isohedrally. This improves on the O(n^{18})-time algorithm of Keating and Vince and generalizes recent work by Brlek, Provençal, Fédou, and the second author.
BibTeX - Entry
@InProceedings{langerman_et_al:LIPIcs:2016:5942,
author = {Stefan Langerman and Andrew Winslow},
title = {{A Quasilinear-Time Algorithm for Tiling the Plane Isohedrally with a Polyomino}},
booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)},
pages = {50:1--50:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-009-5},
ISSN = {1868-8969},
year = {2016},
volume = {51},
editor = {S{\'a}ndor Fekete and Anna Lubiw},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/5942},
URN = {urn:nbn:de:0030-drops-59423},
doi = {10.4230/LIPIcs.SoCG.2016.50},
annote = {Keywords: Plane tiling, polyomino, boundary word, isohedral}
}
| Keywords: | Plane tiling, polyomino, boundary word, isohedral | |
| Seminar: | 32nd International Symposium on Computational Geometry (SoCG 2016) | |
| Issue date: | 2016 | |
| Date of publication: | 10.06.2016 |
