Welcome to MathOverflow

Question

5

1

Question arises from considering cache oblivious algorithms.

What is the optimal way arrange the numbers $1$ to $k^2$ in a grid, to minimize to average difference between any two neighbouring squares? What about minimizing the expected maximum difference between two squares, chosen uniformly? [Joining the edges of the grid to form a torus]

We can do better than just filling in row by row, for instance the Morton layout (for $k = 2^n$), as illustrated below for $k = 16$

$\begin{array}{cccccccc} 1& 2& 5& 6& 17& 18& 21& 22\\ 3& 4& 7& 8& 19& 20& 23& 24\\ 9& 10& 13& 14& 25& 26& 29& 30\\ 11& 12& 15& 16& 27& 28& 31& 32\\ 33& 34& 37& 38& 49& 50& 53& 54\\ 35& 36& 39& 40& 51& 52& 55& 56\\ 41& 42& 45& 46& 57& 58& 61& 62\\ 43& 44& 47& 48& 59& 60& 63& 64\end{array}$

Is there a better layout? I'm sure someone must have thought about this before, but can't seem to find anything relevant.

edited Feb 23 2012 at 22:52

David White
4,860●1●20●27

asked Feb 22 2012 at 23:49

Student
51●1

1

could you define "neighbouring" more precisely? – S. Sra Feb 23 2012 at 1:39

What is "the expected maximum difference between two" random cells in your example? – Joseph O'Rourke Feb 23 2012 at 2:30

2

Note that for $k=2^n$, the "filling in row by row" yields exactly the same average difference as for the Morton layout, viz. $(k+1)/2$. (assuming you mean horizontal and vertical neighbors only). So after all, I'd think there is no better arrangement than "filling in row by row" for the non-torus case. – spanferkel Feb 23 2012 at 18:54

Solve it by brute force programs from 2 by 2 to 4 by 4, maybe higher, and see what you have. For the torus insist on 1 at upper left, such further restrictions as cut down on essentially identical answers. Any cyclic permutation of rows, or of columns, changes nothing in that problem. – Will Jagy Feb 23 2012 at 23:12

spanferkel · Answer 1 · 2012-02-24 11:21:10Z UTC

This is not an answer but too long for a comment. It is a heuristical argument that $\frac{k+1}2$ should be best possible.

It is easy to see that for an optimal arrangement, $1$ and $k^2$ must both occupy corners. Supposing opposite corners, consider the (monotone) lattice paths between them. Each path covers $2(k-1)$ of the differences we are looking for, so the average difference of those is at least $\frac{k^2-1}{2(k-1)}=\frac{k+1}2$ for each such path (equal if the numbers on the path are strictly increasing, greater otherwise).

This is not a proof because summing over all those paths, the differences are not counted equally often. But maybe it can be made into a proof. Problem: if the corners of $1$ and $k^2$ are not opposite, such an argument won't work.

The torus case seems harder, it looks like optimal constuctions may be different for even and odd $k$.

Arrangement of integers 1..k^2 in k*k grid to minimize energy function

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.