rokhsar@lasspvax.UUCP (Dan Rokhsar) (05/06/85)
Newsgroup: net.math Subject: Labeling a lattice Expires: References: Sender: Reply-To: rokhsar@lasspvax.UUCP (Dan Rokhsar) Followup-To: Distribution: Organization: Laboratory of Atomic and Solid State Physics, Cornell University Keywords: Here's a problem related to the "can we map a square to an interval" problem, but with a twist. Consider an N x N square lattice (the generalization to higher dimensions is trivial). We wish to assign a unique integer between 1 and N^2 to each lattice site, so that the maximum difference between adjacent labels is minimized. Boundary conditions can be either free or periodic. Questions: 1. How does the minimum maximal difference (MMD) vary with the size of the square? The dimension of the hypercube? 2. Can we find a rigorous lower bound to the MMD? (by constructing a labeling, we have found that MMD <= (D N)^(D-1) in D dimensions, and by considering the best labeling of a single point and its neighbors, MMD >= (2^D) : a Monte- Carlo approach has yielded an ordering qualitatively similar to the one that gives (D N)^(D-1), at least in 2 dimensions) 3. Is this problem discussed anywhere? if so, could you send us references? One Dimensional Case: An optimal labeling with free boundary conditions is (obviously) 1 2 3 4 5 6 7 8 9 ... (N-2) (N-1) N MMD = 1 With periodic boundary conditions, an optimal one is (for N even) 1 3 5 7 9 ... (N-1) N (N-2) (N-4) ... 6 4 2 MMD = 2 This can be generalized to two and higher dimensions to get our upper bound (left as an exercise to the reader). Dan Rokhsar Steve White
pmontgom@sdcrdcf.UUCP (Peter Montgomery) (05/16/85)
>Consider an N x N square lattice (the generalization to higher dimensions is >trivial). We wish to assign a unique integer between 1 and N^2 to each >lattice site, so that the maximum difference between adjacent labels is >minimized. Boundary conditions can be either free or periodic. > 1. How does the minimum maximal difference (MMD) vary with > the size of the square? The dimension of the hypercube? > 2. Can we find a rigorous lower bound to the MMD? (by constructing > a labeling, we have found that MMD <= (D N)^(D-1) in D > dimensions, and by considering the best labeling of a > single point and its neighbors, MMD >= (2^D) : a Monte- > Carlo approach has yielded an ordering qualitatively similar > to the one that gives (D N)^(D-1), at least in 2 dimensions) > Dan Rokhsar > Steve White The stated lower bound assumes N >= 1. Another lower bound is (N^D-1)/(D*(N-1)). Observe some point is labeled 1 and another point is labeled N^D. There is a path of length at most D*(N-1) connecting these points, hence the bound. Consequently there exist two constants c1(D) and c2(D) such that c1(D) <= MMD(D, N)/N^(D-1) <= c2(D) for all N > 1. -- Peter Montgomery {aero,allegra,bmcg,burdvax,hplabs, ihnp4,psivax,randvax,sdcsvax,trwrb}!sdcrdcf!pmontgom Don't blame me for the crowded freeways - I don't drive.