Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
1  
could you define "neighbouring" more precisely? –  Suvrit Feb 23 '12 at 1:39
    
What is "the expected maximum difference between two" random cells in your example? –  Joseph O'Rourke Feb 23 '12 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. –  Wolfgang Feb 23 '12 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 '12 at 23:12
add comment

1 Answer

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$.

share|improve this answer
    
For the torus, the filling in by rows also yields the same average $\frac{k^2-1}k$ as, for $k=2^n$, the Morton layout! –  Wolfgang Feb 24 '12 at 17:42
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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