4
$\begingroup$

I have a grid of cells, X cells wide by Y cells high. Each cell has four corners, NW, NE, SW and SE. Each corner is shared with adjacent neighbors; i.e., a cell's SW corner is the NW corner of the cell just below it.

In any grid of (X,Y) cells, there are (X+1,Y+1) corners.

In this grid, each corner can be assigned an arbitrary identifier, giving the cell an 'address' of the format NW-NE-SW-SE

In this image below, for cell 'h' the four corners are named @, #, $ and %. The NE corner of cell 'g' would also share the corner name '@'. Cell 'h' would have the address @#$%

grid

What is the minimum number of unique identifiers needed to allow all cells to have a unique 'address'?

Is there a generalized algorithm or pattern one might use to calculate such a list of identifiers and to assign them to all the corners in a grid of size (XY)?

Thanks in advance!

Edited to add: My purpose in asking this question is to solve a real-world problem, which I did not originally state in my question, and further, that I don't necessarily need the theoretical or provable 'minimum set of unique symbols' but rather an algorithm that combines the properties of a) being easy to understand and implement and, b) provides fairly good answers (i.e., small, perhaps not smallest). Very subjective, I know.

$\endgroup$
10
  • 1
    $\begingroup$ I am exploring an approach of identifying the intersection of a camera's center point with a flat surface containing a regular grid of fiducial markers. The camera FOV will always include at least 4 markers. I am trying to ascertain how few unique markers must be used to uniquely identify the camera location. $\endgroup$ Jul 11, 2023 at 22:46
  • $\begingroup$ I believe I have a workable solution that allows as few as (X-1)+(Y-1) unique markers, but the age-old 'four-color map problem' comes to mind and I wonder if there is a better approach. $\endgroup$ Jul 11, 2023 at 22:50
  • $\begingroup$ You can get a solution with X/2 + Y/2 unique markers as follows: Paint rows (of corners) 1 and 2 with one colour, rows 3 and 4 with another, etc., then "overlay" every odd-numbered column with a fresh colour. All cells will then have 2 corners with the same "column colour", and cells in odd-numbered rows will have 2 corners with the same "row colour", while cells in even-numbered rows will have 2 corners with different "row colours". $\endgroup$ Jul 13, 2023 at 12:34
  • $\begingroup$ In fact, you can nearly get a solution with $\sqrt X/2 + \sqrt Y$ unique markers: Let $k$ be the smallest integer such that $k(k-1)\ge Y$ (so $k \simeq \sqrt Y$). Divide the rows into $k$ blocks as follows: Block $i$ has $2(i-1)$ rows. Paint the $i-1$ odd rows in block $i$ all colour $i$, and each of its $i-1$ even rows with a colour $j<i$ (this allows determining the parity of a cell's row). Now "overlay" every odd-numbered column as before, but use just $\sqrt X/2$ fresh colours: For each column, choose a colour pair and use one for even rows and the other for odd. $\endgroup$ Jul 13, 2023 at 13:44
  • 1
    $\begingroup$ This is closely related to de Bruijn tori. $\endgroup$ Jul 13, 2023 at 20:15

4 Answers 4

3
$\begingroup$

You can solve the problem using at most $\left\lceil \sqrt{2X} \right\rceil + \left\lceil \sqrt{2Y} \right\rceil + 3$ identifiers as follows:

PART 1:

Let $G$ be a complete graph over $\left\lceil \sqrt{2X} \right\rceil + 1$ vertices if the $\left\lceil \sqrt{2X} \right\rceil + 1$ is odd; otherwise $G$ be a complete graph over $\left\lceil \sqrt{2X} \right\rceil + 2$ vertices. Each vertex corresponds to a distinct identifier. Note that each vertex in $G$ has even degree. Thus, there exists an Eulerian path in $G$ that can be computed in $O(X)$ time. The path length is at least $X$. In other words, there is a sequence of at least $X$ identifiers such that any pair of consecutive identifiers appears exactly once in the sequence. Lets name this sequence $S_X$.

Use the sequence $S_X$ as the first row of the grid. This ensures that all the cells in the first row have distinct addresses.

Now use the same sequence for each odd numbered row in the grid. This ensures that all the cells within the same row have distinct addresses.

$\text{}$

PART 2:

To ensure that the cells in the same column have distinct addresses, take a new set of $\left\lceil \sqrt{2Y}\right\rceil+1$ identifiers. Let this idetifier set be $I_Y = \{y_1,\dotsc,y_t\}$ for $t = \left\lceil \sqrt{2Y} \right\rceil + 1$. Construct $I_Y \times I_Y$. Let $p = \{y_i,y_j\}$ be any pair of identifiers in $I_Y \times I_Y$. Let $(y_i,y_j,y_i,y_j,\dotsc,y_i)$ be an alternating sequence of these two identifiers. Use this sequence for any even numbered row of the grid. Since there are at least $Y$ such distinct pairs, each grid vertex is now labeled. Note that all the cells in the same column have distinct addresses since they have different $\{y_i,y_j\}$ pairs. Thus all the cells in the grid have the distinct address too. This completes the proof.


Note that you can solve the problem using at most $\left\lceil \sqrt{X} \right\rceil + \left\lceil \sqrt{Y} \right\rceil$ identifiers as well using directional edges in the part $1$ of the above construction and more careful analysis of part $2$.

$\endgroup$
6
  • $\begingroup$ Inuyasha Yagami: Nice answer! Thanks! I'm not super familiar with the mathematical notation... does your final sentence indicate a solution of sqrt(X) + sqrt(Y) identifiers? I see symbols that wrap both that look something like square brackets, but I don't know their significance. $\endgroup$ Jul 17, 2023 at 14:48
  • $\begingroup$ @MikeMetcalf Yes, you can say $\sqrt{X} + \sqrt{Y}$ if both $\sqrt{X}$ and $\sqrt{Y}$ are integers. Since $\sqrt{X}$ could be a fractional value, we choose the smallest integer that is greater than $\sqrt{X}$. For example, if $a = 2.5$, then $\lceil a\rceil = 3$. This is called ceiling function. $\endgroup$ Jul 17, 2023 at 14:53
  • $\begingroup$ Thank you for the explanation. Now that I understand, it seems obvious in retrospect. $\endgroup$ Jul 17, 2023 at 18:28
  • $\begingroup$ This is the best practical solution for large instances, in my opinion. It's quite similar to my comment (I messed up the coefficients there -- fixed in a later comment). In that comment I describe an ordering of colours for rows (the $k$ blocks) that more-or-less corresponds to a concrete Eulerian path here. $\endgroup$ Jul 18, 2023 at 10:45
  • $\begingroup$ @j_random_hacker woww... It is quite similar indeed! I missed that comment. $\endgroup$ Jul 18, 2023 at 11:01
4
$\begingroup$

This is one of the 800 possible optimal (2-colour) solutions (including reflections and rotations) to the 4x4 problem, found using an exhaustive search:

enter image description here

The optimality is because 16 cells require 16 distinct 4-digit labels, which exhausts the set of 4-bit patterns. The next "interesting" problem size (in the sense that a "perfect" solution might be possible) is $3^4=81$ cells (so 9x9, 27x3 or 81x1), which would exhaust all 4-digit base-3 numbers -- but this is much too large to check with a dumb brute-force search.

Larger grids can be tiled with a pattern like this, using fresh pairs of colours for each copy. It's then advantageous to use a slightly less "efficient" base pattern that contains no monochromatic cells (the optimal solution above necessarily contains a blue and a yellow monochromatic cell) -- since then you can reuse each colour with every other colour. In other words, $k$ colours permit $k \choose 2$ copies of the base pattern if it is free of monochromatic cells, rather than just $k/2$ copies.

Tiling-based solutions will in general not be optimal. I don't yet see any better way to attack the problem of finding optimal or boundedly approximate solutions other than brute force on a case-by-case basis with a SAT or ILP solver, as suggested by D.W.

$\endgroup$
5
  • $\begingroup$ To j_random_hacker: could I convince you to compare your answer listed here with the naïve approach I posted below? I suspect you may be onto an approach that performs well and uses an algorithm that is easy-to-understand. $\endgroup$ Jul 13, 2023 at 16:47
  • $\begingroup$ I think I can see the benefits of your tiling approach, which seems to suggest that I can keep adding another 16 cells with the addition of a single new color, but only if those monochromatic cells (f and p) are converted to bi-color cells. Of the other 799 solutions, are there any that do not contain a monochromatic 4-digit label for any cell? $\endgroup$ Jul 14, 2023 at 14:46
  • $\begingroup$ No, all 800 solutions necessarily contain 2 monochromatic cells -- since 4 bits gives you just 16 patterns, and if you only have 16 patterns, two of which (0000 and 1111) correspond to monochromatic cells, there's no way to avoid using both of those patterns if you have 16 cells to cover. $\endgroup$ Jul 18, 2023 at 7:55
  • $\begingroup$ Provided the pattern has no monochromatic cells, using this tiling approach means that every new colour you add gives you the ability to cover as many tiles as colours you already had. E.g., if you had used 100 colours so far, with a 4x3 2-colour base pattern that avoids monochromatic cells, adding a 101st colour would allow you to cover 100 more tiles, i.e., $100\times5\times4=2000$ more cells, since we can use the new colour paired with each of the existing 100 colours. (5x4 because we get an extra horizontal strip of cells between each pair of tiles, and likewise for vertical.) $\endgroup$ Jul 18, 2023 at 9:48
  • $\begingroup$ To simplify, let's assume an $X\times X$ problem instance. With a 4x3 MC-free 2-colour pattern (I'm confident one exists), the above tiling approach yields $X^2/((4+1)\times(3+1))=X^2/20$ tiles, meaning we need at least that many distinct unordered pairs of colours. $k$ colours give $k(k-1)/2$ distinct unordered pairs of colours, so we want the smallest $k$ such that $k(k-1)/2 \ge X^2/20$. For large $k$, $k(k-1)/2\approx k^2/2$, meaning $k\approx 0.32X$ colours. Your posted solution needs $X/2+X/2=X$ colours, so it's a constant factor worse -- but Inuyasha Yagami's is better. $\endgroup$ Jul 18, 2023 at 10:07
2
$\begingroup$

For a pragmatic solution, I suggest using a SAT solver.

Suppose we want to find a valid coloring, using $C$ colors. Let $L=\lceil \lg C \rceil$, so that each color can be encoded as a $L$-bit integer. Let $x_{i,j,k}$ be a boolean variable, representing the $k$th bit of the color of the corner at position $(i,j)$. for each $i,j$, add the constraint that $x_{i,j,L-1} \cdots x_{i,j,1} x_{i,j,0} < C$ as unsigned integers (this can be expressed as CNF clauses). This will force every corner to be colored with one of the $C$ colors.

Also, for each pair of cells, we encode the requirement that those two cells have different 'addresses', as follows: let $y$ denote the sequence of boolean variables that represents the address of the first cell, and $z$ the same for the second cell. We introduce temporary variables $t_0,\dots,t_{4L-1}$, constrain them so that $t_i=y_i \oplus z_i$ ($\oplus$ represents the logical-xor; this can be enforced with a few CNF clauses), and then add the CNF clause $t_0 \lor t_1 \lor \cdots \lor t_{4L-1}$. This will force $y,z$ to differ in at least one bit position, so that the two cells receive different addresses.

Now feed this entire CNF formula to a SAT solver and see if it finds a solution. You can use binary search over $C$ to minimize the number of colors.

A front-end like Z3 will make implementing this easier.

If I had to guess, I would guess that $\sim (XY)^{1/4}$ colors might suffice, but I have no proof.

$\endgroup$
1
  • $\begingroup$ D.W. : Thank you for your response! As a math lay-person, it may take me a while to process your answer. $\endgroup$ Jul 12, 2023 at 14:47
2
$\begingroup$

Each Even column of corners (blue arrows) encodes a single unique ‘X’ indicator: x0,x2,x4… (here colored using Red, Green, Blue)

Each Odd column of corners (yellow arrows) encode a semi-incrementing ‘y’ indicator y0,y0,y1,y1,y2,y2 (here colored using Cyan, Magenta, Yellow)

Resulting set of required unique symbols is (x+1)/2 + (y+1)/2

While I doubt this is an optimal solution for smallest set of unique symbols, it does have the advantage (for my purposes) of being a simple algorithm to implement.

This method seems very similar to the approach suggested by j_random_hacker in a comment above, but I'm not good enough at all this to understand how similar or divergent they actually are.

enter image description here

$\endgroup$
1
  • $\begingroup$ Yes, this looks like the same idea from my first comment, but more clearly stated :) $\endgroup$ Jul 18, 2023 at 7:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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