1
$\begingroup$

A domino tiling is a tesselation of a region in the plane by 2 × 1 squares. What is a good data type for storing and manipulating such objects?

In my current manipulation, use an array to store all the half-squares numbering them 1-2 for a horizontal domino, 3 4 for a vertical. It's not ideal but I can draw the tiling in ASCII or using a graphics editor.

     _ _         _ _
1 2 |_ _|  3 3  | | |
1 2 |_ _|  4 4  |_|_|

In some applications, I have to identify specific features within array. For example, I might have to count all instances of 2 ×2 squares of dominos in my array, excluding things like

 _ _
 _|_   2 1
|_ _|  1 2

These queries are not difficult, but they make me start to question my use of arrays.

$\endgroup$
  • 1
    $\begingroup$ What are the other operations that the data structure should support? $\endgroup$ – saadtaame Jun 5 '14 at 23:16
  • 1
    $\begingroup$ @saadtaame there is a rather complicated operation called "domino shuffling" where the dominos are moving in the coordinate plane. arxiv.org/abs/math/9201305 $\endgroup$ – john mangual Jun 6 '14 at 6:16
3
$\begingroup$

There is an alternative, more compact kind of array representation which might be better if you are working with diamonds as defined in the paper you linked (for axis aligned rectangles you need to find the smallest covering diamond).

The idea is to checkerboard the plane and assign a 2-bit number to each "black" cell, such that the number represents the orientation of the domino relative to the cell. Consider for example: enter image description here

where $0$ means "horizontal domino pointing east", $1$ means "vertical domino pointing north", etc. Tilting the numbers clockwise yields the array representation:

$$A = \begin{pmatrix} 0 & 0 & 0 & 0 \\ 2 & 3 & 3 & 0 \\ 2 & 3 & 0 & 2 \\ 2 & 1 & 0 & 1 \\ 2 & 2 & 2 & 1 \\ \end{pmatrix}$$

To find two dominos forming a square search for a $0$ adjacent to a $2$ or a $1$ adjacent to a $3$. Now, if you deal with big tesselations and are into implemtations sped up by bit operations, you can do this:

Let $A$ be a $\{0,1,2,3\}^{m \times n}$ matrix, $b$ be the bit mask $\dots 01010101$, then we can represent the $i^{th}$ row of $A$ as a single integer by using bit-concatenation:

$$r_i = \bigvee_{j=1}^n (a_{ij} << 2(j-1))$$

where $\vee$ denotes a bitwise OR and $<<$ a leftshift. Denoting $\oplus$ as bitwise XOR we can calculate

$$s_i=(r_i \text{ mod } 2^{2n}) \oplus (r_i >> 2) \oplus b \\ t_i=r_i \oplus r_{i+1} \oplus b, ~~i < m$$

Then domino $a_{ij}$ and domino $a_{ij+1}$ form a square iff bits $(s_i)_{2j-2}$ and $(s_i)_{2j-1}$ are both $1$. Likewise domino $a_{ij}$ and domino $a_{i+1j}$ do so iff bits $(t_i)_{2j-2}$ and $(t_i)_{2j-1}$ are both $1$.

Example calculation for rows 1,2 (little-endian!):

r_1    00 00 00 00
r_2    10 11 11 00
b      01 01 01 01
xor    -----------
       11 10 10 01

Therefore $a_{11}$ and $a_{21}$ form a square.

$\endgroup$
1
$\begingroup$

i had a similar issue in order to store (crossword) puzzle grids, which can have different types of squares (eg letter cells, definition cells, images, etc..)

The representation was this (which can be easily serialized into json)

dimensions:{ rows, columns, etc..}  // for my example this covers almost all default cells 

then a series of attributes describing any cells that are different from default cells

eg.

separators: [{row: r, column: c}, {row: r1, column: c2}, ..], 
images: [{row1: r1, column1: c1, row2: r2, column2: c2, image-data: ..}, ..]

This is only illustrative example, the logic behind this is that the default cells are covered by using just the dimensions and any other types of squares are explicitly described, so in effect this on average should produce minimal representations

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.