5
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ could you define "neighbouring" more precisely? $\endgroup$
    – Suvrit
    Feb 23, 2012 at 1:39
  • $\begingroup$ What is "the expected maximum difference between two" random cells in your example? $\endgroup$
    – Joseph O'Rourke
    Feb 23, 2012 at 2:30
  • 2
    $\begingroup$ 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. $\endgroup$
    – Wolfgang
    Feb 23, 2012 at 18:54
  • $\begingroup$ 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. $\endgroup$
    – Will Jagy
    Feb 23, 2012 at 23:12

1 Answer 1

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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! $\endgroup$
    – Wolfgang
    Feb 24, 2012 at 17:42

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.