Anzeige
Erschienen in:
2005 | OriginalPaper | Buchkapitel
On the Computation of Colored Domino Tilings of Simple and Non-simple Orthogonal Polygons
verfasst von : Chris Worman, Boting Yang
Erschienen in: Algorithms and Computation
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We explore the complexity of computing tilings of orthogonal polygons using colored dominoes. A colored domino is a rotatable 2 × 1 rectangle that is partitioned into two unit squares, which are called faces, each of which is assigned a color. In a colored domino tiling of an orthogonal polygon
P
, a set of dominoes completely covers
P
such that no dominoes overlap and so that adjacent faces have the same color. We describe an
O
(
n
) time algorithm for computing a colored domino tiling of a simple orthogonal polygon, where
n
is the number of dominoes used in the tiling. We also show that deciding whether or not a non-simple orthogonal polygon can be tiled with colored dominoes is NP-complete.