TILING PICTURES OF THE PLANE WITHOUT HOLE S WITH DOMINOES - GRAPHIC FOUNDATION OF THURSTONS ALGORITHM AND PARALLELIZATION

Authors
FOURNIER JC
Citation
Jc. Fournier, TILING PICTURES OF THE PLANE WITHOUT HOLE S WITH DOMINOES - GRAPHIC FOUNDATION OF THURSTONS ALGORITHM AND PARALLELIZATION, Comptes rendus de l'Academie des sciences. Serie 1, Mathematique, 320(1), 1995, pp. 107-112
Citations number
5
Categorie Soggetti
Mathematics, General",Mathematics
Journal title
Comptes rendus de l'Academie des sciences. Serie 1, Mathematique → ACNP
ISSN journal
07644442
Volume
320
Issue
1
Year of publication
1995
Pages
107 - 112
Database
ISI
SICI code
0764-4442(1995)320:1<107:TPOTPW>2.0.ZU;2-L
Abstract
The now classical Thurston's algorithm [4], for tiling finite and with out holes pictures of the plane with dominoes, can be found again by H all's condition for matchings in bipartite graphs and by considering s hortest paths in some graph associated with the picture to tile. This new point of view allows a parallelization in O(log n) time using n(3) processors on a PRAM model, that is in an efficient way (class NC).