Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 9/18/84; site sdcrdcf.UUCP
Path: utzoo!linus!philabs!prls!amdimage!amdcad!amd!pesnta!pertec!scgvaxd!trwrb!sdcrdcf!pmontgom
From: pmontgom@sdcrdcf.UUCP (Peter Montgomery)
Newsgroups: net.math
Subject: Re: Labeling a Lattice
Message-ID: <1985@sdcrdcf.UUCP>
Date: Wed, 15-May-85 20:35:24 EDT
Article-I.D.: sdcrdcf.1985
Posted: Wed May 15 20:35:24 1985
Date-Received: Mon, 20-May-85 04:16:33 EDT
References: <325@lasspvax.UUCP>
Reply-To: pmontgom@sdcrdcf.UUCP (Peter Montgomery)
Organization: System Development Corp. R+D, Santa Monica
Lines: 34


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