Towards Optimal Locality in Mesh-Indexings^{1}

Rolf Niedermeier^{2}

Wilhelm-Schickard-Institut für Informatik, Universität Tübingen,

Sand 13, D-72076 Tübingen, Fed. Rep. of Germany

         niedermr@informatik.uni-tuebingen.de

Klaus Reinhardt^{3}

Wilhelm-Schickard-Institut für Informatik, Universität Tübingen,

Sand 13, D-72076 Tübingen, Fed. Rep. of Germany

         reinhard@informatik.uni-tuebingen.de

Peter Sanders

Fakultät für Informatik, Universität Karlsruhe, D-76128 Karlsruhe, Fed. Rep. of Germany

                  sanders@ira.uka.de

1A preliminary version of parts of this work appear in the proceedings of the 11th International Symposium on Fundamentals of Computation Theory (Springer LNCS 1279, pages 364–375), held in Kraków, Poland, September 1–3, 1997.

2To whom correspondence should be sent. 3Work supported by DFG Project La 618/3-1 KOMET.

Abstract

The efficiency of many data structures and algorithms relies on “locality-preserving” indexing schemes for meshes. We concentrate on the case where the maximal distance between two mesh nodes indexed i and j shall be a slow-growing function of |i−j|. We present a new 2-D indexing scheme we call H-indexing, which has superior (supposedly optimal) locality in comparison with the well-known Hilbert indexings. H-indexings form a Hamiltonian cycle and we prove that they are optimally locality-preserving among all cyclic indexings. We provide fairly tight lower bounds for indexings without any restriction. Further investigations include lower bound results for 3-D mesh indexings. Finally, exemplified by investigations concerning 2-D and 3-D Hilbert indexings, we present a framework for mechanizing upper bound proofs for locality.

Keywords: space-filling curve, self-similar curve, locality-preserving mesh-indexing, locality-preserving grid-indexing

1 Introduction

For many fields in computer science, indexing schemes for meshes, that is, bijective mappings {0, …, n − 1}^{r} → {0, …, n^{r} − 1}, play a crucial role. For example, in computational geometry one often has to map an r-dimensional raster to a one-dimensional traversal order or storage order. In this case, it is often advantageous if close-by raster points have close-by indices [3]. Analogous problems also arise in evaluating differential operators or even in a biological setting [17]. On the other hand, it is also important to consider “locality the other way round.” For example, in parallel processing on mesh-connected computers, one often has to map one-dimensional data structures to the processor-mesh. If the communication requirements within this data structure are predominantly between close-by indices, it is advantageous to map them to close-by processors in order to decrease network contention and latency [5, 6, 18, 21]. In this paper we concentrate on this second kind of locality.

Several mesh-indexing schemes are well-known. Most of these have been developed for the two-dimensional case, but they usually have generalizations for multiple dimensions, for example, row-major or snakelike row-major. However, taking a closer look at applications in parallel processing, one may observe that these kinds of indexings do not preserve locality of computation and communication very well. So, e.g., for an rdimensional mesh with side-length n and row-major indexing, processors 1 and n are at distance n − 1 from each other. Hence, a communication between these two processors ties up n−1 communication links and has a high latency. This is large compared to the distance of about r\sqrt[r]{n} achievable if the first n processors could be arranged in a cube. A locality-preserving indexing should yield a distance f(n) ∈ O(\sqrt[r]{n}). This should generalize to all pairs of processors within the mesh, that is, processors indexed i and j should be at most at distance f(|i−j|) from each other. For example, a simple parallel variant of quicksort can be shown to run in average time Θ ((n + log m)\frac{m}{n^{r}} ) for m ≥ n^{r} elements on n^{r} processors if a locality-preserving indexing scheme is used. This is asymptotically optimal and compared to other asymptotically optimal algorithms only Θ (log n) rather than Θ (n) messages are sent on the critical path [21]. Quicksort, using row-major indexing and related schemes, needs time Θ ((n log n + log m)\frac{m}{n^{r}} ). Various other applications in parallel processing are, e.g., discussed in [6, 13, 16]. Further applications of this kind of locality can be found in image processing and related fields (see [9] and the references cited there). Further discussion of some applications of space-filling curves as mesh indexings can be found in Section 3

In this paper, we improve previous work on locality in mesh-indexings using (discrete) space-filling curves. To analyze locality, we always utilize the three most important metrics in use: Manhattan, Euclidean, and maximum. One of the most important contribution of this paper is the introduction of so-called H-indexings for twodimensional meshes which are based on a variant of the 2-D Sierpiński curve. Hindexings show better locality than Hilbert indexings. Indeed, we conjecture that they are optimally locality-preserving among all space-filling curves. At least, we can show that this holds for the class of cyclic indexings. For H-indexings we prove, for example, that with respect to the Euclidean metric for arbitrary indices i and j, it holds that d(i, j) ≤ \sqrt{4|i − j| − 2}, which is tight up to a small additive constant. This answers an open question of Gotsman and Lindenbaum [9] for the existence of a family of space-filling curves with locality properties better than those of Hilbert curves, where we approximately have a constant factor of \sqrt{6} instead of 2. We also give improved lower bounds for the locality achievable by arbitrary indexings with respect to all three metrics mentioned above and we prove lower bounds for locality in 3-D mesh indexings. Furthermore, we develop a technique for finding upper locality bounds by mechanically inspecting a finite number of cases which is then applied to the 2-D Hilbert indexing and 3-D variants of the Hilbert indexing. This approach enables us to obtain simple and complete proofs of results which which are new or previously relied on difficult to check proofs involving tedious manual case distinctions.

The paper is organized as follows. We introduce some notation in Section 2 and review related work in Section 3. In Section 4 we introduce H-indexings and show that they provide better locality than 2-D Hilbert indexings. The general lower bound which indicates that the H-indexings may indeed be optimal are derived in Section 5. The techniques for mechanically deriving upper bounds is developed in Section 6. This technique is exemplified by a rather simple yet complete proof for the locality properties of the 2-D Hilbert indexing with respect to the Manhattan metric. Then we generalize this method and apply it to 3-D variants of the Hilbert indexing and also include the Euclidean an maximum metrics. Section 7 summarizes the results of the paper and points out possibilities for future research. Finally, in an appendix we give some more complicated proofs of upper bound results given in Section 4 and outline some technical details with respect to indexings for non-orthogonal meshes.

2 Preliminaries

In this paper we work with 2-D and 3-D meshes (or grids, equivalently). We focus attention on quadratic and cubic grids, where, for example, in the 2-D case we have n^{2} points arranged in an n × n-array. Meshes occur in various settings such as parallel computing, data structures, image processing, and many other fields of computer science. In what follows, we restrict the description of some basic concepts to the 2-D case. The generalization to the 3-D ( and r-D) setting is straightforward.

We are interested in indexing schemes for meshes. An indexing scheme simply is a bijective mapping from {0, …, n^{2} − 1} onto {0, …, n − 1} × {0, …, n − 1}, thus providing a total ordering of the mesh points. We will study discrete spacefilling curves as special kinds of indexing schemes, which turn out to have the desired property of preserving locality. To define locality, we first need a metric. We will use the Manhattan, the Euclidean, and the maximum metric, which are defined as follows. Assume that x(i) and y(i) denote the position of a point i within the grid with respect to Cartesian coordinates. Then the Manhattan distance of two grid points i and j is defined as

d_{1}(i, j) := |x(i) − x(j)| + |y(i) − y(j)|,

for the Euclidean distance we have

d_{2}(i, j) := \sqrt{(x(i) − x(j))^{2} + (y(i) − y(j))^{2}},

and the distance according to the maximum metric is

d_{∞}(i, j) := max{|x(i) − x(j)|, |y(i) − y(j)|}.

A discrete space-filling curve C : {0, …, n^{2} − 1} → {0, …, n − 1} × {0, …, n − 1} fulfills d_{2}(C(i), C(i + 1)) = 1. Thus one might say that space-filling curves provide continuous indexings. A space-filling curve traverses the grid making unit steps and turning only at right angles. The meaning will always be clear from the context. Another feature of space-filling curves, besides being continuous, is usually their selfsimilarity. Self-similarity here simply means that the curve can be generated by putting together identical (basic construction) units, only applying rotation and reflection to these units. This will become clearer when considering the construction principles of Hilbert and H-curves in subsequent sections. To simplify presentation, in this paper we will often write i when referring to its geometric location (x(i), y(i)) as well as to its index value. A segment \overline{(i, j)} of a space-filling curve is the set \{C(i), …, C(j)\} of mesh nodes. We deal with the following measure of locality. The basic requirement is that if according to the indexing scheme it holds that |i − j| is small, then d(i, j) shall also be small (applying one of the above metrics). We call a continuous indexing cyclic if d_{2}(0, n^{2} − 1) = 1. In this case, we compute modulo n^{2} − 1, i.e., we use the additive group ({0, …, n^{2} − 1}, +) for adding and subtracting indices. Also, for cyclic indexings |i| shall denote the distance from i to 0, thus |i| ≤ n^{2}/2. Informally speaking, these assumptions express that for cyclic indexings we do not care at which node the numbering starts.

3 Related Work

In this section we provide some links to related literature. We cite a few recent papers from various fields dealing with locality questions for meshes and using space-filling curves as indexing schemes. In particular, we pay special attention to the field of parallel processing and give a short account of the development of locality-preserving indexings in this field.

There are basically two aspects of locality studied for meshes. Locality as studied by us requires that the smaller the absolute value of the difference between two points i and j is, i.e., |i − j|, the smaller d(i, j) shall be. This kind of locality is important in many areas, we refer to two recent papers in parallel processing [6] and image processing [9]. Locality “the other way round,” namely requiring that small d(i, j) shall imply small |i−j| is e.g. studied by Mitchison and Durbin [17], who present some optimal results for this setting. Refer also the paper of Gotsman and Lindenbaum [9] for a short discussion of various locality measures and related results. However, whenever the demand for whatever kind of locality in mesh indexings arose, nearly always spacefilling curves and, particularly, Hilbert indexings came into play [3, 4, 5, 6, 8, 9, 11, 19, 21]. Besides the applications described later, locality-preserving indexing schemes are also useful whenever geometrical data is to be mapped to a one-dimensional domain, e.g, in parallel gravitational particle simulation [22], for graph partitioning [12] and fast range queries for geometrical data stored on disks [3, 4].

In what follows we will concentrate on the first kind of locality as mentioned above. There are three kinds of metrics used for d(i, j)—Euclidean, maximum, and Manhattan. The Euclidean metric particularly plays an important role in fields like image processing and computer graphics. We refer to the recent paper of Gotsman and Lindenbaum [9]. They mainly studied Hilbert’s space-filling curve and provide upper and lower bounds. We will improve their upper and lower bounds in the 2-D case.

As to the Manhattan metric, it has particular importance in the field of parallel processing on mesh-connected processor arrays. Here good locality of an indexing scheme for the processors may lead to reduced communication costs [5, 6, 13, 16, 21]. (The same holds for the maximum metric, which is more suitable for grids with diagonal connections, cf. e.g. [14, 15].) For the Manhattan metric and the field of parallel processing, we delve into more detail about the history of results and applications. Stout [23] seems to be the first who used so-called proximity orderings in the context of 2-D mesh algorithms. We call them Hilbert indexings due to the direct relation to Hilbert’s space-filling curve [10, 20]. Subsequently, they have been used to speed up a wide variety of parallel algorithms: computational geometry [16], fast backtracking and branch-and-bound [13], mapping of pyramid networks [7], simulation of abstract parallel computation models [6, 18], and parallel quicksort [21]. Quantitative analysis of the properties of locality-preserving indexing schemes have, so far, focused mainly on the 2-D Hilbert-indexing. According to Stout “there is a constant c < 4 such that processors numbered i and j are no more than c·\sqrt{|i − j|} communication links apart” [23, page 27]. Such a claim for c = 4 was later proved by Kaklamanis and Persiano [13] (although they apparently did not know of Miller and Stout’s work [16, 23]). Recently, a bound of 3 · \sqrt{|i − j|} has been proved by Chochia, Cole, and Heywood [6]. However, the proof is quite complicated. We present a fairly simple and complete proof of this result and show that H-curves, to be introduced in the next section, beat Hilbert curves with respect to locality. Very recently, Chochia and Cole [5] also provided results for 3-D Hilbert indexings, which also will be complemented by our results.

4 The H-Indexing

Gotsman and Lindenbaum [9, page 797] asked “whether there exist families of spacefilling curves with locality properties better than those of the Hilbert curves for all sizes.” One of the main contributions of this paper is to answer this question affirmatively. Moreover, our result not only holds for the Euclidean metric as studied by Gotsman and Lindenbaum, but also for the Manhattan and the maximum metrics. In this section we introduce H-indexings and analyze their locality properties showing the claimed improvement compared to Hilbert indexings. The next section will advocate that H-indexings are optimally locality-preserving among all discrete space-filling curves by giving tight lower bounds.

4.1 Construction scheme

H-indexings are related to 2-D Sierpiński curves [20]. As the naming indicates, Hindexings have an “H-shaped” form. In analogy to Hilbert indexings, we obtain indexings for 2^{k}×2^{k}-meshes^{1} by an inductive method. There is, however, a decisive difference. Whereas in the case of Hilbert indexings the building blocks are four smaller squares (cf. Section 6 and Figure 7 there), the construction of H-indexings is easier to describe using right-angled triangles. As for Hilbert indexings we only have one building block to which we apply rotation or reflection. To build the final mesh indexing, we put together two triangles. Fig. 1 shows the construction of a triangle from 4 smaller triangles. A triangle with 8 mesh nodes is constructed from triangles with only two nodes and a triangle with 32 nodes is constructed from those with 8 nodes. Observe that the Figure 1: H-indexings are built using triangles as building blocks.

1A Java program for the general case of non-cubic meshes with arbitrary side-lengths can be found at http://www-fs.informatik.uni-tuebingen.de/~reinhard/hcurve.html.

Figure 2: Building an H-indexing for a square using two triangles.

triangles are constructed in such a way that exactly each other mesh node along the diagonal belongs to the nodes of the triangle. Thus an indexing scheme for a square mesh can be obtained as shown in Fig. 2. In an alternative way, Fig. 3 shows how for all k > 1 an H-indexing through a square of size 4^{k} is built from 4 H-indexings through squares of size 4^{k−1} each. For subsequent proofs, however, it is more convenient to make use of the construction principle based on triangles as described above.

More formally, we can describe the H-indexing of an 2^{k} × 2^{k} mesh by expressing the coordinates of the i-th point recursively in the following way (also see Figure 4). Observe that the subsequent parameter l is uniquely determined in each recursive step

Figure 3: Inductive construction principle of H-indexings.

2^{k} { 0 f _{2^{2k} − 1}^{2g}  ^{4g}_{2h}  _{7g}^{g}j  ^{3g} _{5g}  _{6g}_{h} i _{3h}  _{} 2^{l}}

Figure 4: The positions of the points i and j for the worst cases. The recursion is shown for l = k − 1. Let g = 2^{2l−1} and h = 2^{2l−3}.

by the if-conditions of the various cases; l ranges from k − 1 to 1.

x(i) = \{ \begin{matrix}2^{k} − 1 − x(i − 2^{2k−1}) & if & i ≥ 2^{2k−1}, \\ 2^{l} + x(i − 3 · 2^{2l−1}) & if & 4 · 2^{2l−1} > i ≥ 3 · 2^{2l−1}, \\ 2^{l} − 1 − x(3 · 2^{2l−1} − 1 − i) & if & 3 · 2^{2l−1} > i ≥ 2 · 2^{2l−1}, \\ x(2^{2l} − 1 − i) & if & 2 · 2^{2l−1} > i ≥ 1 · 2^{2l−1}, \\ 0 & if & i ≤ 1. \end{matrix}

y(i) = \{ \begin{matrix}2^{k} − 1 − y(i − 2^{2k−1}) & if & i ≥ 2^{2k−1}, \\ 2^{l} + y(i − 3 · 2^{2l−1}) & if & 4 · 2^{2l−1} > i ≥ 3 · 2^{2l−1}, \\ 2^{l} + y(3 · 2^{2l−1} − 1 − i) & if & 3 · 2^{2l−1} > i ≥ 2 · 2^{2l−1}, \\ 2^{l+1} − 1 − y(2^{2l} − 1 − i) & if & 2 · 2^{2l−1} > i ≥ 1 · 2^{2l−1}, \\ i & if & i ≤ 1. \end{matrix}

The following results for worst cases are to be compared with the subsequent Theorem 1 presenting upper bounds for the locality of H-indexings. The Euclidean worst case (cf. Figure 4) for each k are pairs of points i = 3 · 2^{2k−5} − 1 and j = 2^{2k−3} + 1 with |i − j| = 2^{2k−5} + 2 and

d_{2}(i, j) = \sqrt{(x(i) − x(j))^{2} + (y(i) − y(j))^{2}}
= \sqrt{(2^{k−2} − 1 − 2^{k−1} + 2)^{2} + (2^{k−2} − 2^{k−1} − 1)^{2}}
= \sqrt{4(2^{2k−5} + 2) − 8 + 2} = \sqrt{4|i − j| − 6}.

The same pairs are also responsible for the worst case in Manhattan metric:

d_{1}(i, j) = |x(i) − x(j)| + |y(i) − y(j)|
= −2^{k−2} + 1 + 2^{k−1} − 2 − 2^{k−2} + 2^{k−1} + 1 = 2^{k−1}
= \sqrt{8 · 2^{2k−5}} = \sqrt{8(|i − j| − 2)}.

Thus in both cases we observe the worst cases on a diagonal direction (from i to j). But in the maximum metric, the worst cases are from 0 to f = 2^{2k−2} − 1 (see Figure 4) with |0 − f| = 2^{2k−2} − 1 and

d_{∞}(i, j) = 2^{k} − 1 = 2\sqrt{|0 − f| + 1} − 1.

4.2 Upper bounds

In this subsection we give results for locality properties of H-indexings with respect to the Euclidean, the Manhattan, and the maximum metric. As it turns out, proofs that give tight results including additive constants are fairly complicated and are therefore deferred to the appendix. Here we state only the results.

Theorem 1. For two arbitrary indices i and j, i ≠ j, on the H-indexing the following holds:

1. d_{1}(i, j) ≤ \sqrt{8(|i − j| − 2)} for |i − j| > 3,

2. d_{2}(i, j) ≤ \sqrt{4|i − j| − 2},

3. d_{∞}(i, j) ≤ 2\sqrt{|i − j| + 1} − 1.

Theorem 1 shows that H-indexings provide an improvement in locality compared to Hilbert-curves, answering an open question of Gotsman and Lindenbaum [9]. Focusing their attention on the Euclidean metric, they proved that for Hilbert curves C with respect to their locality measure L_{1}(C) := max_{i,j∈{1,... ,n^{2}},i<j} d_{2}(i, j)^{2}/|i − j| it holds 6 · (1 − O(2^{−k})) ≤ L_{1}(C) ≤ 20/3, where n = 2^{k} with k > 1. Our result implies that for H-indexings C we have L_{1}(C) = 4. To present our result of Theorem 1, we preferred to make a more concrete and more precise statement (which even includes additive constants) than the “L_{1}(C)-notation” allows.

Both maximum metric and Manhattan metric are of particular relevance in parallel processing [6, 18, 21]. In particular, a further advantage of H-indexings over Hilbert indexings is that they not just describe a Hamiltonian path but a Hamiltonian cycle through the mesh. This is, e.g., useful for parallel algorithms which employ communication along a virtual ring network. Interestingly, H-indexings are optimally locality-preserving among all Hamiltonian cycles through a square mesh, as the next section shows.

Although it is complicated to prove Theorem 1 as such, it is fairly easy to prove an only slightly weaker version, which only involves slightly weaker additive constants.

Theorem 2. For two arbitrary indices i and j on the H-indexing the following holds:

1. d_{1}(i, j) ≤ \sqrt{8|i − j|} + 4,

2. d_{2}(i, j) ≤ 2\sqrt{|i − j|} + \sqrt{10},

5′,7′ 0312  45 6 7 0′ 1′,3′  2′,6′ 4′

Figure 5: Indexing nodes ({0, 1, 2, 3, 4, 5, 6, 7}) in a triangle of size 8 and their representatives ({0′, 1′, 2′, 3′, 4′, 5′, 6′, 7′}). Note that 1′ and 3′ have the same location and so on.

3. d_{∞}(i, j) ≤ 2\sqrt{|i − j|} + 3.

Proof. We concentrate on proving the result for the Euclidean metric d_{2}(i, j). The statements for the Manhattan metric d_{1}(i, j) and the maximum metric d_{∞}(i, j) then easily follow by the general relations

d_{1}(i, j) ≤ \sqrt{2} · d_{2}(i, j)

and

d_{∞}(i, j) ≤ d_{2}(i, j).

The proof for d_{2}(i, j) works by induction on the size of the smallest triangle (according to the construction principle of H-curves) that contains both i and j. Note that all these triangles are right-angled and contain 2^{l} mesh points with l ≥ 1. Hence the induction operates on l. For l = 1 and l = 2 the claim can be trivially checked. Consider a triangle of size 8 (8-triangle for short), that is, l = 3, as drawn in Fig. 5. To each of the nodes in an 8-triangle nodes we assign a representative lying at the corners of the 4 subtriangles as drawn in Fig. 5. The rule behind this assignment is that the two representatives of a 2-triangle are determined as follows: If possible, rotate the 2-triangle in such a way that it has the same orientation (the vertical cathetus to the left, the horizontal cathetus to the bottom) as the original 8-triangle. The two representatives are then (in the case of Fig. 5) at the endpoints of the vertical cathetus. Observe that in Fig. 5 the 2-triangle containing nodes 4 and 5 cannot be rotated in such a way that it has the same orientation as the 8-triangle. In this case, we speak of the complementary triangle and here the endpoints lie on the horizontal cathetus. Note that each right-angled triangle can be brought (by rotation) in one of the orientations “one cathetus as bottom line and one cathetus either to the left or to the right as vertical line.”

Let i and j be two arbitrary nodes and let l > 2. Let i′ and j′ be the representatives of i and j, respectively. We show by induction on l that

d_{2}(i′, j′) ≤ 2\sqrt{|i′ − j′|}. (∗)

p  i′  j′

Figure 6: Two representatives in the two halves of the smallest triangle containing both of them.

Observe that the numerical values of i and i′ resp. j and j′ are the same, only their geometric positions differ a little. In particular, we introduce the convention that a “2^{l}-triangle” may contain 2^{l} +1 representatives, where the 2^{l} +1st is also the first node of the subsequent triangle. This assumption is solely due to technical reasons. From (∗) our claim immediately follows, because the Euclidean distance between an index i and its representative i′ (for example, 2 and 2′) may be at most \sqrt{(1/2)^{2} + (3/2)^{2}} = \sqrt{10}/2. Hence

d_{2}(i, j) ≤ d_{2}(i′, j′) + \sqrt{10}.

In the Manhattan case we have

d_{1}(i, j) ≤ d_{1}(i′, j′) + 4

and in the maximum case we have

d_{∞}(i, j) ≤ d_{∞}(i′, j′) + 3.

It remains to prove inequality (∗) by induction on l. The claim for l = 1 and l = 2 can be easily checked (cf. Fig. 5). Now let i′ and j′ be in two different halves of their (smallest) “surrounding” triangle (otherwise the induction hypothesis applies). Due to our definition of representatives we can assume (up to rotation) a situation as drawn in Fig. 6. In Fig. 6, the point p located at the right angle always exists and the angle between i′, p, and j′ is always bounded by 90^{o}. Thus the Euclidean distance between i′ and j′ can be bounded from above using Pythagoras’ theorem and the induction hypothesis:

d_{2}(i′, j′) ≤ \sqrt{d_{2}^{2}(i′, p) + d_{2}^{2}(p, j′)}
≤ \sqrt{4|i′ − p| + 4|p − j′|}
= 2\sqrt{|i′ − j′|}.

This verifies inequality (∗) and the proof is completed.

In the next section we show that H-indexings are at least close to providing optimal locality in mesh-indexings.

5 Lower Bounds

This section indicates that H-indexings might be optimal in locality-preservation among all indexings of 2-D meshes. Indeed, we conjecture that they are optimal for the Euclidean, the maximum and the Manhattan metric. Because the difficulty for a general proof lies in “coming to grips with the loose ends,” we advocate this conjecture by showing the optimality among the cyclic indexings. Furthermore, we also provide lower bounds for indexings of 3-D meshes.

5.1 Euclidean and maximum metric

Theorem 1 of Gotsman and Lindenbaum [9] says that for any discrete 2-D space-filling curve on an n × n-mesh, it holds d_{2}(i, j) > \sqrt{3(1 − 1/n)^{2}|i − j|}. They also report that by a computerized exhaustive search they have improved the constant factor 3 to 3.25. We improve this to 3.5 by a direct proof. In addition, their result only holds for continuous indexings, whereas ours poses no restrictions concerning the indexing. We conjecture that this can be raised to 4, which would imply the optimality of H-curves among all mesh-indexings (cf. Theorem 1 and Theorem 2).

In the following theorem we make use of the general relationship d_{∞}(i, j) ≤ d_{2}(i, j) by only proving the result for the maximum metric.

Theorem 3. For each indexing of an n×n-mesh, n ≥ 2, there must be indices i and j with d_{2}(i, j), d_{∞}(i, j) > n/4 such that d_{2}(i, j), d_{∞}(i, j) ≥ \sqrt{3.5|i − j|} − 1.

Proof. Due to d_{2}(i, j) ≥ d_{∞}(i, j) it suffices to restrict our attention to the maximum metric. Assume on the contrary that for all i and j with d_{∞}(i, j) > n/4 we have d_{∞}(i, j) < \sqrt{3.5|i − j|} − 1, that means |i − j| > (d_{∞}(i, j) + 1)^{2}/3.5. Let i_{1} < i_{2} < i_{3} and i_{2} < i_{4} be the indices of the 4 corner points of the n × n-mesh. Since we leave the relation between i_{3} and i_{4} open, the following describes (except for symmetric cases) all possibilities (cf. [9]). Note that the right-hand picture is necessary for the case of non-continuous indexings.

i^{1} i_{2}  i^{4} i_{3} i^{0} i^{5}  ^{i^{1} i_{3}  i^{4} i_{2} i^{0} i^{5}}

Let i_{0} be the rightmost point on the line between i_{1} and i_{4} with i_{0} < i_{2} and distance m − 1 from i_{1}. Therefore the neighboring point i_{5} with i_{2} < i_{5} has distance n − m − 1 from i_{4}. We have two possible orders of i_{0} and i_{1} and six possible orders of i_{3}, i_{4} and i_{5}. Thus, assuming n/4 < m < 3n/4 in order to be able to make use of our assumption |i − j| > ((d_{2}(i, j) + 1)^{2})/3.5, we have the following relationship. Observe that the following is valid for both pictures above at the same time.

n^{2} ≥ min{|i_{0} − i_{1}| + |i_{1} − i_{2}|, |i_{1} − i_{0}| + |i_{0} − i_{2}|}

+ min{|i_{2} − i_{3}| + |i_{3} − i_{4}| + |i_{4} − i_{5}|, |i_{2} − i_{3}| + |i_{3} − i_{5}| + |i_{5} − i_{4}|, |i_{2} − i_{5}| + |i_{5} − i_{4}| + |i_{4} − i_{3}|, |i_{2} − i_{5}| + |i_{5} − i_{3}| + |i_{3} − i_{4}|, |i_{2} − i_{4}| + |i_{4} − i_{3}| + |i_{3} − i_{5}|, |i_{2} − i_{4}| + |i_{4} − i_{5}| + |i_{3} − i_{3}|}

> min\{\frac{(d_{∞}(i_{0}, i_{1}) + 1)^{2} + (d_{∞}(i_{1}, i_{2}) + 1)^{2}}{3.5} , \frac{(d_{∞}(i_{1}, i_{0}) + 1)^{2} + (d_{∞}(i_{0}, i_{2}) + 1)^{2}}{3.5} \}

+ min\{\frac{(d_{∞}(i_{2}, i_{3}) + 1)^{2} + (d_{∞}(i_{3}, i_{4}) + 1)^{2} + (d_{∞}(i_{4}, i_{5}) + 1)^{2}}{3.5} ,

\frac{(d_{∞}(i_{2}, i_{3}) + 1)^{2} + (d_{∞}(i_{3}, i_{5}) + 1)^{2} + (d_{∞}(i_{5}, i_{4}) + 1)^{2}}{3.5} ,

\frac{(d_{∞}(i_{2}, i_{5}) + 1)^{2} + (d_{∞}(i_{5}, i_{4}) + 1)^{2} + (d_{∞}(i_{4}, i_{3}) + 1)^{2}}{3.5} ,

\frac{(d_{∞}(i_{2}, i_{5}) + 1)^{2} + (d_{∞}(i_{5}, i_{3}) + 1)^{2} + (d_{∞}(i_{3}, i_{4}) + 1)^{2}}{3.5} ,

\frac{(d_{∞}(i_{2}, i_{4}) + 1)^{2} + (d_{∞}(i_{4}, i_{3}) + 1)^{2} + (d_{∞}(i_{3}, i_{5}) + 1)^{2}}{3.5} ,

\frac{(d_{∞}(i_{2}, i_{4}) + 1)^{2} + (d_{∞}(i_{4}, i_{5}) + 1)^{2} + (d_{∞}(i_{5}, i_{3}) + 1)^{2}}{3.5} \}

= \frac{m^{2} + n^{2}}{3.5}

+ min\{\frac{2n^{2} + (n − m)^{2}}{3.5} , \frac{2n^{2} + (n − m)^{2}}{3.5} , \frac{n^{2} + (n − m)^{2} + n^{2}}{3.5} ,

\frac{3n^{2}}{3.5} , \frac{3n^{2}}{3.5} , \frac{n^{2} + (n − m)^{2} + n^{2}}{3.5} \}

= \frac{m^{2} + 3n^{2} + (n − m)^{2}}{3.5} = \frac{2m^{2} + 4n^{2} − 2nm}{3.5} = \frac{3.5n^{2} + 2(n/2 − m)^{2}}{3.5}

On the other hand, if m ≤ n/4, by eliminating i_{0} we get

n^{2} ≥ \frac{3n^{2} + (n − m)^{2}}{3.5} ≥ \frac{3n^{2} + (3n/4)^{2}}{3.5} = \frac{3.5625n^{2}}{3.5} .

Analogously, if m ≥ 3n/4, by eliminating i_{5} we get

n^{2} ≥ \frac{m^{2} + 3n^{2}}{3.5} ≥ \frac{3n^{2} + (3n/4)^{2}}{3.5} = \frac{3.5625n^{2}}{3.5} .

Each case leads to a contradiction.

The lower bound for cyclic indexings can be obtained fairly easily. Together with Theorem 1 it shows optimality of H-indexings up to small additive constants.

Theorem 4. For each cyclic indexing of an n×n-mesh, n ≥ 2, there must be indices i and j such that d_{2}(i, j), d_{∞}(i, j) ≥ 2\sqrt{|i − j|} − 1. In particular, this lower bound holds for two corners i and j of the mesh.

Proof. Let i_{1}, i_{2}, i_{3}, and i_{4} be the 4 corner points of an n × n-mesh. Because the indexing is cyclic (and thus also continuous, cf. Section 2) there must be two corner points i_{j} and i_{k} with j, k ∈ { 1, 2, 3, 4 } and j ≠ k such that |i_{j} − i_{k}| ≤ n^{2}/4. On the other hand, it holds d_{2}(i_{j}, i_{k}) ≥ d_{∞}(i_{j}, i_{k}) ≥ n − 1 ≥ 2\sqrt{|i_{j} − i_{k}|} − 1.

5.2 Manhattan metric

Whereas in the case of the Euclidean and the maximum metric we could give quite close bounds also for the “general case,” this seems to be more difficult in the case of the Manhattan metric. In the general case we obtain the following, comparatively weaker result:

Theorem 5. For each indexing of an n × n-mesh, n ≥ 2, there must be indices i and j with d_{1}(i, j) > 2n/5 such that d_{1}(i, j) ≥ \sqrt{6.5|i − j|} − 2.

Proof. Assume on the contrary that for all i and j with d_{1}(i, j) > 2n/5 we have d_{1}(i, j) < \sqrt{6.5|i − j|} − 2, that means |i − j| > (d_{1}(i, j) + 2)^{2}/6.5. Let i_{1} < i_{2} < i_{5} < i_{6} be the indices of the 4 corner points of the n×n-mesh the indexing passes through in the given order. Then (except for symmetric cases) we have the following five possibilities. Observe that the first picture comes into play because we also allow non-continuous indexings.

i^{1} i_{5}  i^{6} i_{2}  ^{i^{1} i_{2}  i^{5} i_{6} i^{0} i^{3} i_{4} i_{7}}  ^{i^{1} i_{2}  i^{5} i_{6} i^{0} i^{4} i_{3} i_{7}}

i^{1} i_{2}  i^{6} i_{5} i^{0}i^{3} i^{4}i^{7}  ^{i^{1} i_{2}  i^{6} i_{5} i^{0} i^{7}}

Here i_{0} is the rightmost point on the horizontal line containing i_{1} with i_{0} < i_{2} and distance m − 1 from i_{1}, and i_{7} is the leftmost point on the horizontal line containing i_{6} with i_{5} < i_{7} and distance l − 1 from i_{6}. Moreover, i_{3} and i_{4} are direct left respectively right neighbors of i_{0} and i_{7} with i_{3} < i_{4}.

The case exhibited with the first picture is fairly easy to handle. Needing no further assumptions, we have

n^{2} ≥ |i_{1} − i_{6}| = |i_{1} − i_{2}| + |i_{2} − i_{5}| + |i_{5} − i_{6}|
> \frac{(d_{1}(i_{1}, i_{2}) + 2)^{2} + (d_{1}(i_{2}, i_{5}) + 2)^{2} + (d_{1}(i_{5}, i_{6}) + 2)^{2}}{6.5}
≥ \frac{4n^{2} + n^{2} + 4n^{2}}{6.5} = \frac{9n^{2}}{6.5} ,

a contradiction.

In the case referring to the second picture, we have

n^{2} ≥ |i_{0} − i_{7}| = |i_{0} − i_{2}| + |i_{2} − i_{3}| + |i_{3} − i_{4}| + |i_{4} − i_{5}| + |i_{5} − i_{7}|
> \frac{(d_{1}(i_{0}, i_{2}) + 2)^{2} + (d_{1}(i_{2}, i_{3}) + 2)^{2} + (d_{1}(i_{3}, i_{4}) + 2)^{2}}{6.5}

+\frac{(d_{1}(i_{4}, i_{5}) + 2)^{2} + (d_{1}(i_{5}, i_{7}) + 2)^{2}}{6.5}

≥ \frac{(n + m)^{2} + (n + m)^{2} + (2n − m − l)^{2} + (n + l)^{2} + (n + l)^{2}}{6.5}
= \frac{8n^{2} + 3m^{2} + 2ml + 3l^{2}}{6.5} ≥ \frac{8n^{2}}{6.5} .

In the third picture, if m + l ≥ n/2 then

n^{2} ≥ |i_{0} − i_{7}| = |i_{0} − i_{2}| + |i_{2} − i_{5}| + |i_{5} − i_{7}|
> \frac{(n + m)^{2} + 4n^{2} + (n + l)^{2}}{6.5} = \frac{6n^{2} + 2(m + l)n + m^{2} + l^{2}}{6.5} ≥ \frac{7n^{2}}{6.5} ,

else (i.e., m + l < n/2) we have to distinguish between three sub-cases. First assume that i_{3} < i_{1}. Then

n^{2} ≥ |i_{3} − i_{5}| = |i_{3} − i_{1}| + |i_{1} − i_{2}| + |i_{2} − i_{5}|
> \frac{(2n − l)^{2} + n^{2} + (2n)^{2}}{6.5} = \frac{9n^{2} − 4ln + l^{2}}{6.5} ≥ \frac{7n^{2}}{6.5} .

If i_{3} < i_{1}, then we further distinguish between i_{4} < i_{6} and i_{4} > i_{6}. If i_{4} < i_{6}, then

n^{2} ≥ |i_{1} − i_{6}| = |i_{1} − i_{3}| + |i_{3} − i_{4}| + |i_{4} − i_{6}|
> \frac{(2n − l)^{2} + n^{2} + (2n − m)^{2}}{6.5} ≥ \frac{9n^{2} − 4(m + l)n}{6.5} ≥ \frac{7n^{2}}{6.5} .

Finally, if i_{4} > i_{6}, we then have

n^{2} ≥ |i_{2} − i_{4}| = |i_{2} − i_{5}| + |i_{5} − i_{6}| + |i_{6} − i_{4}|
> \frac{(2n)^{2} + n^{2} + (2n − m)^{2}}{6.5} = \frac{9n^{2} − 4mn + m^{2}}{6.5} ≥ \frac{7n^{2}}{6.5} .

With respect to the fourth picture, let w.l.o.g. m ≤ l. Then

n^{2} ≥ |i_{0} − i_{7}| = |i_{0} − i_{2}| + |i_{2} − i_{3}| + |i_{3} − i_{5}| + |i_{5} − i_{7}|
> \frac{(n + m)^{2} + (n + m)^{2} + (2n − m)^{2} + (n + l)^{2}}{6.5}
≥ \frac{7n^{2} + 4m^{2} + 6nm − 4nm}{6.5} ≥ \frac{7n^{2}}{6.5} .

In the last picture, the difference to the fourth case is that i_{0} and i_{7} are now direct neighbors. In addition, for symmetry reasons (interchange the roles of i_{0} and i_{7}) we w.l.o.g. assume that m ≤ n/2. If m ≤ 0.418n, then

n^{2} ≥ |i_{1} − i_{7}| = |i_{1} − i_{5}| + |i_{5} − i_{7}|
> \frac{(2n)^{2} + (1.582n)^{2}}{6.5} = \frac{(4 + 2.502)n^{2}}{6.5} .

If i_{0} < i_{1} and m > 0.418n, then

n^{2} ≥ |i_{0} − i_{7}| = |i_{0} − i_{1}| + |i_{1} − i_{5}| + |i_{5} − i_{7}|
> \frac{m^{2} + (2n)^{2} + (2n − m)^{2}}{6.5} = \frac{8n^{2} + 2m^{2} − 4nm}{6.5}
= \frac{6.5n^{2} + (n − 2m)^{2}/2 + (n − 2m)n}{6.5} ≥ \frac{6.5n^{2}}{6.5} .

If i_{7} < i_{6} then

n^{2} ≥ |i_{1} − i_{6}| = |i_{1} − i_{5}| + |i_{5} − i_{7}| + |i_{7} − i_{6}|
> \frac{(2n)^{2} + (1.5n)^{2} + (0.5n)^{2}}{6.5} = \frac{(4 + 2.25 + 0.25)n^{2}}{6.5} .

Otherwise we have 0.418n < m ≤ n/2, i_{1} < i_{0}, and i_{6} < i_{7}. Then

n^{2} ≥ |i_{1} − i_{7}| = |i_{1} − i_{0}| + |i_{0} − i_{2}| + |i_{2} − i_{6}| + |i_{6} − i_{7}|
> \frac{m^{2} + (n + m)^{2} + (2n)^{2} + (n − m)^{2}}{6.5} = \frac{6n^{2} + 3m^{2}}{6.5} > \frac{6.5n^{2}}{6.5} ,

again a contradiction. This completes the proof.

In the special cyclic case, however, we can again prove (asymptotic) optimality of H-curves due to the following theorem.

Theorem 6. For each cyclic indexing of an n × n-mesh, n ≥ 2, there must be indices i and j such that |i − j| ≤ n^{2}/2 and d_{1}(i, j) ≥ \sqrt{8|i − j|} − 2. In particular, this lower bound holds if i and j are in two diagonally opposite corners of the mesh.

Proof. Since the indexing in a cycle is regarded as modulo the number of nodes (cf. Section 2), we have |i − j| ≤ n^{2}/2 for any i and j in an n × n square. For two diagonally opposite corners i and j we thus have d_{1}(i, j) = 2n − 2 ≥ 2\sqrt{2|i − j|} − 2 = \sqrt{8|i − j|} − 2.

5.3 Omitting surjectivity

So far for the lower bounds we considered bijective indexings, which fill the mesh completely. On the other hand, in practical situations it could happen that the grid has more nodes than we have to embed. In this case we can construct a curve filling only a non-orthogonal square of the form

and this can indeed be done by the same inductive recursion principle as for the H-curve (see Appendix, part B). Of course this will not help for the Euclidean metric, since the worst case (the two points lying at the endpoints of the hypotenuse of a triangle) has the same factor in any orientation, but the other two metrics are dependent from the orientation, which allows a slight improvement. This reveals that surjectivity is necessary for Theorem 4 (maximum case) and Theorem 6.

5.4 The bounds for 3 dimensions

We conclude this section by providing lower bounds for 3-D n × n × n-meshes.

Theorem 7. For each indexing of an n × n × n-mesh, n ≥ 2, there must be indices i and j with d(i, j) > n/4 for all three metrics such that the lower bounds of the following table hold.

d(i, j) Euclidean maximum Manhattan
General lower bound \sqrt[3]{11.1|i − j|} − \sqrt{3} \sqrt[3]{8.25|i − j|} − 1 \sqrt[3]{42.625|i − j|} − 3
Cyclic lower bound \sqrt[3]{12.39|i − j|} − \sqrt{3}  \sqrt[3]{9|i − j|} − 1  \sqrt[3]{54|i − j|} − 3

In particular, the cyclic lower bounds hold for i and j being on a corner or an edge of the 3-D mesh.

Proof. We start with the cyclic lower bound for the Manhattan metric. For any i and j we have |i − j| ≤ n^{3}/2. For two diagonally opposite corners i and j we have d_{1}(i, j) = 3n − 3 ≥ 3\sqrt[3]{2|i − j|} − 3 = \sqrt[3]{54|i − j|} − 3.

For all the other five cases we first assume the contrary (cf. the proof of Theorem 5) for all i and j and lead this to a contradiction.

For the non-cyclic Manhattan case, consider the corners i_{1}, …, i_{6} of a cube

i_{1} i_{7} i_{6}  i_{5}  i_{4} i_{3} i_{2}

For symmetry reasons, we can assume w.l.o.g. i_{1} < i_{3} < i_{6}. If i_{4} < i_{1}, then

n^{3} ≥ |i_{4} − i_{3}| = |i_{4} − i_{1}| + |i_{1} − i_{3}| + |i_{3} − i_{6}| > \frac{(3n)^{3} + (2n)^{3} + (3n)^{3}}{42.625} = n^{3} \frac{62}{42.625},

a contradiction. If i_{6} < i_{4}, then

n^{3} ≥ |i_{1} − i_{4}| = |i_{1} − i_{3}| + |i_{3} − i_{6}| + |i_{6} − i_{4}| > \frac{(2n)^{3} + (3n)^{3} + (2n)^{3}}{42.625} = n^{3} \frac{43}{42.625}.

If i_{1} < i_{4} < i_{3}, then

n^{3} ≥ |i_{1} − i_{6}| = |i_{1} − i_{4}| + |i_{4} − i_{3}| + |i_{3} − i_{6}| > \frac{(3n)^{3} + n^{3} + (3n)^{3}}{42.625} = n^{3} \frac{55}{42.625}.

Let d_{1}(i_{1}, i_{7}) = n/2. If i_{3} < i_{7} < i_{4}, then

n^{3} ≥ |i_{1} − i_{6}| = |i_{1} − i_{3}| + |i_{3} − i_{7}| + |i_{7} − i_{4}| + |i_{4} − i_{6}|
> \frac{(2n)^{3} + (2.5n)^{3} + (2.5n)^{3} + (2n)^{3}}{42.625} = n^{3} \frac{47.25}{42.625}.

If i_{4} < i_{7} (otherwise, consider |i_{7} − i_{3}| + |i_{3} + i_{6}|), then

n^{3} ≥ |i_{1} − i_{7}| = |i_{1} − i_{4}| + |i_{4} − i_{7}| > \frac{(3n)^{3} + (2.5n)^{3}}{42.625} = n^{3} \frac{42.625}{42.625}.

Now we consider the maximum metric for the cyclic (non-cyclic) case. Let i_{1} < i_{2} < … < i_{8} be the indices of the corner points. Since at most 8 (7) of the 12 edges lead from i_{j} to i_{j+1}, regarding the points on these edges as additional reference points would have no effect. Let us therefore consider the remaining 4 (5) edges leading from i_{k} to i_{l} with |k − l| > 1 for k, l ∈ {1, …, 8}.

For all k and l, let i_{k,l} be the point with i_{k,l} < i_{l−1} or i_{k,l} > i_{l+1} on the edge from i_{k} to i_{l} that is next to i_{l}, and let m_{k,l} − 1 be the distance from i_{k} to i_{k,l}. Note that the following picture shows the only possibility where i_{k,l} is left to i_{l,k}, which implies that they are direct neighbors. Furthermore, observe that the picture only shows sample positions for the points i_{k−1}, i_{k+1}, i_{l−1}, and i_{l+1}—other positions are possible, too. Clearly m_{k,l} + m_{l,k} ≥ n.

i_{k−1} i_{k+1} i_{k} i_{k,l} i_{l,k} i_{l+1} i_{l}  i_{l−1}

Now consider the estimation of n^{3} as the sum of all |i_{j} − i_{j+1}| for j = 1, …, 8 (7), which is (in the cyclic case, using the assumption |i_{j} − i_{j+1}| > (d_{∞}(i_{j}, i_{j+1}) + 1)^{3}/9; the non-cyclic case works analogously) 8n^{3}/9 (7n^{3}/8.25). If we insert i_{k,l} in this chain, we increase the sum by at least m_{k,l}^{3} for the distance from i_{k} to i_{k,l}; the distance from i_{k,l} to the other corner point is still n − 1. Together with inserting i_{l,k}, we increase by at least m_{k,l}^{3} + m_{l,k}^{3}, which is ≥ 0.25n^{3} since m_{k,l} + m_{l,k} ≥ n. (For the case that i_{k,l} < i_{k−1} or i_{k,l} > i_{k+1}, we will even get an increase by n^{3}.) Doing this for 4 (5) such edges will increase the sum to 9n^{3}/9 (8.25n^{3}/8.25) leading to the contradiction.

A problem with this method can occur if i_{k} and i_{k+1} are both neighboring corners of i_{l} with i_{k−2} ≠ i_{l} ≠ i_{k+2}, then we take only one of the points i_{k,l} or i_{k+1,l}—depending on whether m_{k,l} or m_{k+1,l} is bigger—as additional reference point. But in this case the way from i_{k} to i_{k+1} is no edge of the cube; this means that the number of edges that are available to define a pair of reference points is even greater than 4 (5).

Finally, we come to the Euclidean metric. We start with the cyclic case. Let i_{1} < i_{2} < … < i_{8} again be the indices of the corner points; here we distinguish between 2 cases: If i_{j} is the opposite corner to i_{j+4} for every j ∈ {1, …, 4}, then following the indexing, we have three intermediate corners on the way to the opposite corner. However, a way from a corner to its opposite corner using only edges of the cube would always have an even number of intermediate corners, therefore one way must go diagonally over a plane of the cube, which means w.l.o.g. d_{2}(i_{1}, i_{2}) = d_{2}(i_{5}, i_{6}) = (n−1)\sqrt{2}. The following picture illustrates this situation for the points i_{1}, i_{2}, i_{5}, and i_{6}.

i_{1}  i_{4} i_{3}  i_{8} i_{2}  i_{5} i_{7} i_{6}

Furthermore, w.l.o.g. d_{2}(i_{2}, i_{4}) = d_{2}(i_{6}, i_{8}) = (n − 1)\sqrt{2}. Now we can estimate

n^{3} ≥ |i_{1} − i_{2}| + |i_{2} − i_{4}| + |i_{4} − i_{5}| + |i_{5} − i_{6}| + |i_{6} − i_{8}| + |i_{8} − i_{1}|
> \frac{4(n\sqrt{2})^{3} + 2n^{3}}{12.39} > n^{3} \frac{13}{12.39}.

Otherwise, w.l.o.g. i_{1} is opposite to i_{j} and i_{k} is opposite to i_{l} with 1 < j < k < l. Thus we can estimate

n^{3} ≥ |i_{1} − i_{j}| + |i_{j} − i_{k}| + |i_{k} − i_{l}| + |i_{l} − i_{1}| > \frac{(n\sqrt{3})^{3} + n^{3} + (n\sqrt{3})^{3} + n^{3}}{12.39} > n^{3} \frac{12.39}{12.39}.

In the non-cyclic case with the corner points i_{1} < … < i_{8} we again distinguish between two main cases: If d_{2}(i_{j}, i_{j+1}) = n − 1 for all j ∈ {1, …, 7}, then we have two subcases: If d_{2}(i_{1}, i_{4}) = d_{2}(i_{5}, i_{8}) = \sqrt{3}(n − 1) (shown in the left picture below), then

n^{3} ≥ |i_{1} − i_{4}| + |i_{4} − i_{5}| + |i_{5} − i_{8}| > \frac{2(n\sqrt{3})^{3} + n^{3}}{11.1} ≥ n^{3} \frac{11.39}{11.1}.

i_{1}  i_{3} i_{8}  i_{6} i_{7}  i_{4} i_{5} i_{2}  i_{2}  i_{4} i_{1}  i_{7} i_{9} i_{0}  i_{8}  i_{5} i_{6} i_{3}  i_{2}  i_{4} i_{1}  i_{7} i_{9} i_{0}  i_{6}  i_{5} i_{8} i_{3}

Otherwise (see right two pictures), we have d_{2}(i_{2}, i_{5}) = d_{2}(i_{4}, i_{7}) = \sqrt{3}(n − 1). Let i_{9} be the point on the middle of the line between i_{2} and i_{7}. If i_{4} < i_{9} < i_{5}, then

n^{3} ≥ |i_{1} − i_{2}| + |i_{2} − i_{4}| + |i_{4} − i_{9}| + |i_{9} − i_{5}| + |i_{5} − i_{7}| + |i_{7} − i_{8}|
> \frac{n^{3} + (n\sqrt{2})^{3} + 2(n\sqrt{2.25})^{3} + (n\sqrt{2})^{3} + n^{3}}{11.1} = n^{3}2\frac{\sqrt{2.25}^{3} + \sqrt{2}^{3} + 1}{11.1} > n^{3} \frac{14.4}{11.1}.

If not i_{4} < i_{9} < i_{5}, then w.l.o.g. we may assume i_{5} < i_{9}. If i_{8} < i_{9}, then

n^{3} ≥ |i_{1} − i_{2}| + |i_{2} − i_{5}| + |i_{5} − i_{7}| + |i_{7} − i_{8}| + |i_{8} − i_{9}|
> \frac{n^{3} + (n\sqrt{3})^{3} + (n\sqrt{2})^{3} + n^{3} + (n\sqrt{1.25})^{3}}{11.1}
= n^{3} \frac{1 + \sqrt{3}^{3} + \sqrt{2}^{3} + 1 + \sqrt{1.25}^{3}}{11.1} > n^{3} \frac{11.4}{11.1},

else let i_{0} be the point on the line between i_{1} and i_{8} (respectively. i_{6}) with distance ⌈0.307n − 1⌉ from i_{1}. If i_{0} < i_{2}, then

n^{3} ≥ |i_{0} − i_{2}| + |i_{2} − i_{5}| + |i_{5} − i_{9}| + |i_{9} − i_{8}|
> \frac{(n\sqrt{1.094})^{3} + (n\sqrt{3})^{3} + (n\sqrt{2.25})^{3} + (n\sqrt{1.25})^{3}}{11.1}
= n^{3} \frac{\sqrt{1.094}^{3} + \sqrt{3}^{3} + \sqrt{2.25}^{3} + \sqrt{1.25}^{3}}{11.1} > n^{3} \frac{11.11}{11.1},

else if i_{0} > i_{6} (the cases i_{2} < i_{0} < i_{6} lead to even bigger sums), then

n^{3} ≥ |i_{1} − i_{2}| + |i_{2} − i_{5}| + |i_{5} − i_{6}| + max{|i_{6} − i_{0}|, |i_{8} − i_{0}|}
> \frac{n^{3} + (n\sqrt{3})^{3} + n^{3} + (n\sqrt{2.48})^{3}}{11.1} ≥ n^{3} \frac{1 + \sqrt{3}^{3} + 1 + \sqrt{2.48}^{3}}{11.1} > n^{3} \frac{11.1}{11.1}.

In the second main case we have d_{2}(i_{j}, i_{j+1}) ≥ \sqrt{2}(n − 1) for a j ∈ \{1, …, 7\}. If j is odd, then we know that there is an even number of corners before i_{j} and an even number of corners after i_{j+1}. Thus we can make our estimation using at least four diagonals through a plane, yielding

n^{3} > \frac{4(n\sqrt{2})^{3}}{11.1} ≥ n^{3} \frac{11.31}{11.1}.

If d_{2}(i_{j′}, i_{j′+1}) ≥ \sqrt{2}(n − 1) for a j′ ∈ \{1, …, j − 1, j + 1, …, 7\}, we can estimate

n^{3} > \frac{3(n\sqrt{2})^{3} + 3n^{3}}{11.1} ≥ n^{3} \frac{11.48}{11.1}.

If d_{2}(i_{j−1}, i_{j+1}) = \sqrt{3}(n − 1) or d_{2}(i_{j}, i_{j+2}) = \sqrt{3}(n − 1), we can estimate

n^{3} > \frac{(n\sqrt{3})^{3} + 2(n\sqrt{2})^{3} + n^{3}}{11.1} ≥ n^{3} \frac{11.85}{11.1}.

In the remaining cases i_{j−1}, i_{j}, i_{j+1}, and i_{j+2} form a “Z” on one plane of the cube. If j = 4 (in the following the left and the middle picture), then if i_{1} is the opposite corner of i_{4}, then

n^{3} ≥ |i_{1} − i_{4}| + |i_{4} − i_{5}| + |i_{5} − i_{8}|
> \frac{(n\sqrt{3})^{3} + (n\sqrt{2})^{3} + (n\sqrt{3})^{3}}{11.1} = n^{3} \frac{2\sqrt{3}^{3} + \sqrt{2}^{3} + 1}{11.1} > n^{3} \frac{13.22}{11.1},

i_{1}  i_{3} i_{2}  i_{7} i_{8}  i_{4} i_{6} i_{5}  i_{8}  i_{3}^{i_{0}}^{i_{9}} i_{2}  i_{7} i_{1}  i_{4} i_{6} i_{5}  i_{6}  i_{1} i_{0} i_{7}  i_{5} i_{8}  i_{2} i_{4} i_{3}

else i_{8} must be the opposite corner of i_{4}. Let i_{0} be the point on the edge from i_{2} to i_{8} next to i_{8} with i_{0} < i_{4} having distance m − 1 from i_{2} and let i_{9} be the lower neighbor, then

n^{3} ≥ min{|i_{0} − i_{1}| + |i_{1} − i_{2}| + |i_{2} − i_{4}|, |i_{1} − i_{0}| + |i_{0} − i_{4}|}

+ min{|i_{4} − i_{5}| + |i_{5} − i_{6}| + |i_{6} − i_{9}|, |i_{4} − i_{9}| + |i_{9} − i_{6}| + |i_{6} − i_{8}|}

> \frac{min\{\sqrt{n^{2} + m^{2}}^{3} + n^{3} + (n\sqrt{2})^{3}, \sqrt{n^{2} + m^{2}}^{3} + \sqrt{2n^{2} + m^{2}}^{3}\}}{11.1}

+ min\{\frac{(n\sqrt{2})^{3} + n^{3} + \sqrt{2n^{2} + (n − m)^{2}}^{3}}{11.1} ,

\frac{\sqrt{2n^{2} + m^{2}}^{3} + \sqrt{2n^{2} + (n − m)^{2}}^{3} + (n\sqrt{2})^{3}}{11.1} \}

= \frac{min\{\sqrt{n^{2} + m^{2}}^{3} + n^{3} + (n\sqrt{2})^{3}, \sqrt{n^{2} + m^{2}}^{3} + \sqrt{2n^{2} + m^{2}}^{3}\}}{11.1}

+\frac{(n\sqrt{2})^{3} + n^{3} + \sqrt{2n^{2} + (n − m)^{2}}^{3}}{11.1}

≥ n^{3} \frac{min\{2 + \sqrt{2}^{3} + \sqrt{2}^{3} + 1 + \sqrt{2}^{3}, 1 + 2\sqrt{2.25}^{3} + \sqrt{2}^{3} + 1\}}{11.1} =
≥ n^{3} \frac{min\{11.48, 11.57\}}{11.1}.

Otherwise (j ≠ 4, see the right picture above), we may assume w.l.o.g. j = 2. Let i_{0} be the point in the middle on the edge from i_{1} to i_{7}. If i_{0} < i_{2}, then

n^{3} ≥ |i_{0} − i_{2}| + |i_{2} − i_{3}| + |i_{3} − i_{4}| + |i_{4} − i_{7}| + |i_{7} − i_{8}|
> \frac{(n\sqrt{1.25})^{3} + (n\sqrt{2})^{3} + n^{3} + (n\sqrt{3})^{3} + n^{3}}{11.1}
= n^{3} \frac{\sqrt{1.25}^{3} + \sqrt{3}^{3} + \sqrt{2}^{3} + 2}{11.1} > n^{3} \frac{11.42}{11.1}

else if i_{5} < i_{0} < i_{8} (the cases i_{2} < i_{0} < i_{5} or i_{8} < i_{0} lead to even bigger sums), then

n^{3} ≥ |i_{1} − i_{2}| + |i_{2} − i_{3}| + |i_{3} − i_{5}| + |i_{5} − i_{0}| + |i_{0} − i_{8}|
> \frac{n^{3} + 2(n\sqrt{2})^{3} + (n\sqrt{2.25})^{3} + (n\sqrt{1.25})^{3}}{11.1}
= n^{3} \frac{1 + 2\sqrt{2}^{3} + 1 + \sqrt{2.25}^{3} + \sqrt{1.25}^{3}}{11.1} > n^{3} \frac{11.42}{11.1}.

Thus all cases led to contradictions, finishing the proof.

6 Mechanizing proofs for upper bounds

The main intent of this section is to introduce a technique which makes it possible to derive locality properties of self-similar indexings by mechanical inspection. In Section 6.1, we start with the well know 2-D Hilbert indexing and give a more complete proof of the tight bound for the Manhattan distance already found in [6] which does not need tedious manual case distinctions. Then, in Section 6.2 we develop a more general technique and apply it to other metrics and to 3-D Hilbert indexings.

Figure 7: Hilbert indexings of size 4 and 16 and the general construction principle.

6.1 The Hilbert indexing

Fig. 7-(a) shows the two smallest Hilbert indexings for meshes of size 4 and 16. Figure 7-(b) shows the general construction principle. For any k ≥ 1 four Hilbert indexings of size 4^{k} are combined into an indexing of size 4^{k+1} by rotating and reflecting them in such a way that concatenating the indexings yields a Hamiltonian path through the mesh. Note that the left and the right side of the curve are symmetric to each other. So we only need to keep track of the orientation of the edge which contains the start and end of the curve (drawn with bold lines here).^{2} We start with a lower bound for the locality:

Theorem 8. For every k ≥ 1, there are indices i and j on the Hilbert indexing such that |i − j| = 4^{k−1} and the Manhattan-distance of i and j is exactly 3\sqrt{|i − j|} − 2 = 3 · 2^{k−1} − 2.

i  2^{ki1}  2^{k}  j

Figure 8: Worst-case for the Manhattan-distance between two indices i and j.

Proof. Consider Fig. 8. It shows parts of the Hilbert indexing (rotated right by 90 degrees compared to Fig. 7). It suffices to show that the indices i and j in the lower left and upper right corner of the shaded area of Fig. 8 have Manhattandistance 3\sqrt{|i − j|} − 2. We must compute the size of the shaded area which denotes all nodes on the Hilbert indexing lying between i and j. We always draw the largest subsquare filled by the Hilbert indexing on the path from i to j. In this sense, the dotted line represents the path of the Hilbert indexing respecting the sizes of the largest subsquares it passes through. Except for the lower left corner and upper right corner we have exactly three subsquares of size 2^{l} × 2^{l} within the shaded area for each 0 ≤ l < k − 1. Because the shaded area of the left half can be mapped to the unshaded area in the right half of Fig. 8 (except for one mesh node remaining), we get |i − j| = 4^{k−1}. Computing 3\sqrt{|i − j|} − 2 = 3 · 2^{k−1} − 2, we obtain exactly the Manhattan-distance of i and j, where the latter can easily be read from Fig. 8.

2We note without proof that the above rule uniquely defines the Hilbert indexing up to global rotation and reflection. In a sense, the Hilbert curve is the “simplest” self-similar, recursive, localitypreserving indexing scheme for square meshes of size 2^{k} × 2^{k}. More details can be found in [2].

Before we come to the matching upper bound, we need a technical lemma that shows how we can bound max_{|i−j|=m} d(i, j) for a fixed m by inspecting a finite number of segments. Namely the segments of length m which either lie within a single indexing of size 4^{⌈log_{4} m⌉} or within two such sub-grids which can only have 4 different relative orientations. This method works for an arbitrary norm ∥·∥.

Lemma 9. Let x(i) and y(i) denote the x-coordinate and y-coordinate of the ith point in the Hilbert indexing. Let

d_{int}(m) := max {d(i, j) : |i − j| = m ∧ 0 ≤ i < j < 4^{⌈log_{4} m⌉}} and
d_{ext}(m) := max_{0≤n<m} max ( \begin{matrix}∥(1+y(n)+x(m−n−1),x(n)−y(m−n−1))∥ \\ ∥(1+y(n)+y(m−n−1),x(n)−x(m−n−1))∥ \\ ∥(1+x(n)+y(m−n−1),y(n)−x(m−n−1))∥ \\ ∥(1+x(n)+x(m−n−1),y(n)−y(m−n−1))∥ \end{matrix} ) .

Then ∀i, j : d(i, j) ≤ max(d_{int}(|i − j|), d_{ext}(|i − j|)).

Proof. Consider any segment size m and any indices i and j with |i − j| = m. W.l.o.g. assume j > i and let k = ⌈log_{4} m⌉.

(1) Case ¬∃l ∈ {i + 1, …, j} : l ≡ 0 mod 4^{k}: Due to the self-similarity of the Hilbert indexing, the segment \overline{(i, j)} is isomorphic to the segment \overline{(i mod 4^{k}, j mod 4^{k})} and this segment has been checked by computing d_{int}(m).

(2) All other cases: There is exactly one l with i < l ≤ j and l ≡ 0 mod 4^{k}. Due to the self-similarity and symmetry of the Hilbert-indexing the segments \overline{(l, j)} and \overline{(i, l − 1)} are isomorphic to the segments \overline{(0, j − l)} and \overline{(0, l − i − 1)} respectively. There are only four different (disregarding rotation and reflection) ways the segments \overline{(l, j)} and \overline{(i, l − 1)} can be oriented towards each other. The distances stemming from these four subcases have been checked by computing d_{ext}. Figure 9 shows these possibilities.

This result will be later used in its full generality. It should be emphasized here that Lemma 9 can be employed mechanically by a simple computer program. But for now, we concentrate on the Manhattan metric:

Theorem 10. For the Manhattan-distance of two arbitrary indices i and j on the Hilbert indexing with i ≠ j, we have d_{1}(i, j) ≤ 3\sqrt{|i − j|} − 2.

Proof. The basic idea is to exploit the self-similarity of the Hilbert indexing for an inductive proof over |i − j|. In principle, the proof is quite simple. However, it turns

j′  |y(j′) − y(i′)| |y(j′) − x(i′)| x(j′) 1  1  11 i′ i′ x(i′) y(i′)  x(j′) y(j′) y(j′) x(i′)  y(i′) i′ j′  j′ i′ |x(j′) − x(i′)| |x(j′) − y(i′)|  j′

Figure 9: Possible relative orientations of two Hilbert-squares, where i′ corresponds to the term l − i − 1 in the proof of Lemma 9 and j′ corresponds to j − l.

out that a special treatment is necessary for “small” meshes and for indices i and j which are close to the worst case described in Theorem 8.

(1) Case |i − j| < 16: By inspection. E.g. by applying Lemma 9.

(2) Case |i − j| ≥ 16: By induction over |i − j| we prove the following stronger statement: d_{1}(i, j) ≤ 3\sqrt{|i − j|} − 2.5 or i and j are arranged as in Theorem 8 (Fig. 8) and d_{1}(i, j) = 3\sqrt{|i − j|} − 2.

(2.1) Basis of induction, 16 ≤ |i − j| ≤ 80: By inspection. Note that Lemma 9 can be applied mechanically by a simple computer program.

(2.2) Inductive step for |i − j| > 80: We look at the “coarsened” indexing defined by considering each 2×2 subsquare starting at even coordinates as a single mesh node. Due to the self-similarity of the Hilbert indexing, the coarsened indexing is itself a Hilbert indexing. Define a ∈ ℕ and b ∈ {0, 1, 2, 3} such that i = 4a + b, and c ∈ ℕ and d ∈ {0, 1, 2, 3} such that j = 4c + d. In the coarsened indexing, the positions of i and j are a and c. Since |a − c| ≥ 16, we can apply the induction hypothesis. Furthermore, d_{1}(i, j) ≤ 2 · d_{1}(a, c) + 2 because for each of the four mesh-positions in subsquare a there is a corresponding mesh-position in subsquare c which is 2 · d_{1}(a, c) steps away; at worst j can be another two steps away from the mesh-position corresponding to i. We now distinguish two cases regarding the relative positions of a and c.

(2.2.1) a and c are not arranged as in Theorem 8: By the induction hypothesis we have d_{1}(a, c) ≤ 3\sqrt{|a − c|} − 2.5 and therefore d_{1}(i, j) ≤ 2(3\sqrt{|a − c|} − 2.5) + 2 = 6\sqrt{|a − c|} − 3 . Substituting a = \frac{i−b}{4} and c = \frac{j−d}{4} we get |a − c| = \frac{|(i−b)−(j−d)|}{4} ≤ \frac{|i−j|+|d−b|}{4} ≤ \frac{|i−j|+3}{4} and therefore d_{1}(i, j) ≤ 3\sqrt{|i − j| + 3} − 3. A simple calculation shows that 3\sqrt{|i − j| + 3} ≤ 3\sqrt{|i − j|} + 0.5 for |i − j| ≥ 80 and therefore d_{1}(i, j) ≤ 3\sqrt{|i − j|} − 2.5.

(2.2.2) a and c are arranged as in Theorem 8: Up to symmetric cases the 2 × 2-subsquares for i and j are numbered ( \begin{matrix}0 & 3 \\ 1 & 2 \end{matrix} ) and ( \begin{matrix}0 & 1 \\ 3 & 2 \end{matrix} ) and the subsquare for j is above and to the right of the subsquare for i (refer to Fig. 8). There are two subcases:

(2.2.2.a) b = d = 1: i and j are also arranged as in Theorem 8 and therefore d_{1}(i, j) = 3\sqrt{|i − j|} − 2.

(2.2.2.b) Else: We can use the estimate d_{1}(i, j) ≤ 2d_{1}(a, c) + 1 because the worst case in which d_{1}(i, j) = 2d_{1}(a, c) + 2 has already been covered by the case b = d = 1. A similar calculation as before now shows that d_{1}(i, j) ≤ 2(3\sqrt{|a − c|} − 2) + 1 = 6\sqrt{|a − c|} − 3 ≤ 3\sqrt{|i − j|} − 2.5.

6.2 A Generalized Technique and its Applications

There are few places where the proof of Theorem 10 makes explicit use of the properties of the Hilbert indexing or the Manhattan metric. We now present a generalized technique which can be applied to a wide spectrum of self-similar indexings in r-dimensional meshes made up of building blocks of size q_{1}, …, q_{r} and a norm ∥·∥. For simplicity, however, we restrict the presentation to cubic building blocks with side-length q and only show how slightly looser upper bounds than that of Theorem 10 can be proved. The latter relaxation allows us to avoid the special treatment of the worst case segments which is necessary in the proof of Theorem 10.

Theorem 11. Given any indexing scheme for r-dimensional meshes with the property that combining each elementary cube of size q^{r} in a mesh of size q^{kr} into a single metanode yields the indexing for a mesh of size q^{(k−1)r}: If ∀q^{(k−1)r} ≤ |i − j| ≤ q^{kr} : d(i, j) ≤ α(\sqrt[r]{|i − j|} − δ) − β

where β := ∥(1, …, 1)∥ and δ ≥ \frac{\sqrt[r]{q^{kr} + q^{r} − 1} − q^{k}}{q − 1}

then ∀|i − j| ≥ q^{(k−1)r} : d(i, j) ≤ α(\sqrt[r]{|i − j|} − δ) − β.

The Proof of Theorem 11 is quite analogous to the Proof of Theorem 10:

Proof. By induction over |i − j|. Let a = ⌊i/q^{r}⌋, b = i mod q^{r}, c = ⌊j/q^{r}⌋, and d = j mod q^{r}. Due to the self-similarity of the indexing scheme, we can apply the induction hypothesis to a and c if |i − j| ≥ q^{kr}. We have d(i, j) ≤ q · d(a, c) + β(q − 1) because for each of the q^{r} mesh-positions in subcube a there is a corresponding meshposition in subcube c which is q · d(a, c) steps away; at worst j can be another β(q − 1) steps away from the mesh-position corresponding to i (the diameter of a cube of side length q). By the induction hypothesis we have d(a, c) ≤ α(\sqrt[r]{|a − c|} − δ) − β and therefore

d(i, j) ≤ q(α(\sqrt[r]{|a − c|} − δ) − β) + β(q − 1) = q · α(\sqrt[r]{|a − c|} − δ) − β .

Substituting a = \frac{i−b}{q^{r}} and c = \frac{j−d}{q^{r}} we get

|a − c| = \frac{|(i − b) − (j − d)|}{q^{r}} ≤ \frac{|i − j| + |d − b|}{q^{r}} ≤ \frac{|i − j| + q^{r} − 1}{q^{r}}

and therefore d(i, j) ≤ α(\sqrt[r]{|i − j| + q^{r} − 1} − qδ) − β. A simple calculation shows that

\sqrt[r]{|i − j| + q^{r} − 1} − qδ ≤ \sqrt[r]{|i − j|} − δ for |i − j| ≥ q^{kr} and δ ≥ ^{\frac{\sqrt[r]{q^{kr}+q^{r}−1}−q^{k}}{q−1}} .

Figure 10: Relative cube orientations to be checked for bounding maximum distances for a given segment size.

Theorem 11 can be applied to yield upper bounds for d(i, j). However, the additive constant δ and—except for the Manhattan metric—the additive constant β are artifacts of the inductive proof. If we do not want to make case distinctions involving special properties of worst case segments as in the proof of Theorem 10, we have to accept a small increase in the multiplicative factor α which compensates for the additive constants if |i − j| is large. The case of small |i − j| can be resolved by inspection. Consider the following procedure for obtaining bounds of the form d(i, j) ≤ α\sqrt[r]{|i − j|}+ c where c is some constant to be determined.

• Determine q and r from the definition of the indexing.

• Fix a k.

• Set δ = \frac{\sqrt[r]{q^{kr} + q^{r} − 1} − q^{k}}{q − 1} and β := ∥(1, …, 1)∥.

• Exploit the self-similarity of the indexing to find an analog to Lemma 9 which makes it possible to bound d(i, j) for indices with |i − j| = m using some mechanizable method.

• Find a constant α such that d(i, j) ≤ α(\sqrt[r]{|i − j|}−δ)−β for q^{(k−1)r} ≤ |i−j| ≤ q^{kr}. Applying Theorem 11 we can infer that the same is true for |i − j| ≥ q^{kr}, i.e. ∀|i − j| ≥ q^{(k−1)r} : d(i, j) ≤ α(\sqrt[r]{|i − j|} − δ) − β ≤ α\sqrt[r]{|i − j|} − β.

• Find a constant c ≥ −β such that d(i, j) ≤ α\sqrt[r]{|i − j|} + c for |i − j| ≤ q^{(k−1)r}.

• We can now conclude from the two points above that for all i, j, d(i, j) ≤ α\sqrt[r]{|i − j|} + c.

In what follows, we will simply use c = 0 (which will always suffice) in order to reflect that the additive constants are not tight. Also, we will only cite the tightest constant factor for an upper bound as given by our method without reiterating that the constructive nature of the method also yields a lower bound with a close-by constant factor.

2-D Hilbert indexings

Using the above method and by applying a small computer program^{3} to the case k = 8, we can infer a bound for the Euclid metric of d_{2}(i, j) ≤ \sqrt{6 + 0.01}\sqrt{|i − j|} which is very close the lower bound of \sqrt{6|i − j| − 2} − 1 due to Gotsman and Lindenbaum [9]

and a significant improvement over the upper bound d_{2}(i, j) ≤ \sqrt{6 + \frac{2}{3}} \sqrt{|i − j|} derived in the same paper.

Trivially, the same bound also applies to the maximum metric for which Gotsman and Lindenbaum reported the same constant factors of \sqrt{6} and \sqrt{6 + \frac{2}{3}} for lower and upper bounds respectively.

Symmetric 3-D Hilbert indexings

Figure 11: Rule for building 3-D Hilbert indexings of order k from indexings of order k − 1. The bottom front edge of the new cube is distinguished by the fact that the indexing starts and ends there. The corresponding edges of the component cubes are drawn with thick lines. The order k − 1 cubes have to be rotated accordingly.

We have also applied the above technique to the three variants of a 3-D Hilbert indexing shown in Fig. 11. Up to rotation and reflections these are the only variants which are symmetric with respect to an axis. The maximum segment distances can be checked in complete analogy to Lemma 9: Now nine relative orientations are to be checked.^{4}

Applying the “method” for variants (b) and (c) with k = 5 yields d_{1}(i, j) ≤ 4.820661\sqrt[3]{|i − j|} and the systematic search discovers indices with d_{1}(i, j) ≥ 4.820248\sqrt[3]{|i − j|}. Variant (a) has slightly better locality: d_{1}(i, j) ≤ 4.6161\sqrt[3]{|i − j|}−3 for large |i − j| and the same holds for small |i − j| using a slightly looser additive constant. In comparison, the best analytic bound derived in [5] has the constant factor 8/\sqrt[3]{4} ≈ 5.04.

Variant (a) is also slightly superior for the Euclidean metric where we get d_{2}(i, j) ≤ 3.212991\sqrt[3]{|i − j|} for variant (a) and d_{2}(i, j) ≤ 3.245222\sqrt[3]{|i − j|} for variants (b) and (c) when we apply a simple program^{5} for k = 4. As opposed to the 2-D case, the maximum metric allows smaller bounds than the Euclidean metric in the 3-D case. We get d_{∞}(i, j) ≤ 3.076598\sqrt[3]{|i − j|} for variant (a) and d_{∞}(i, j) ≤ 3.104403\sqrt[3]{|i − j|} for variants (b) and (c).^{6}

3Available under http://liinwww.ira.uka.de/~sanders/hilbert/euclid2.c.

4A C-program doing the necessary checks is available under http://liinwww.ira.uka.de/ ~sanders/hilbert/check3d.c.

5Available under http://liinwww.ira.uka.de/~sanders/hilbert/euclid3d.c.

The method could also be applied to the asymmetric variants of the Hilbert indexing described in [5]. We need only to change the procedure for checking maximum segment sizes to take segments starting at both ends of a cube indexing into account. Even generalizations to more complicated schemes like the H^{∗} indexing described in [5] seem possible. (This scheme appears to have a better locality than simple Hilbert indexings.) H^{∗} uses two non-isomorphic building blocks to define larger indexings. But it still has the crucial property, that replacing a 2 × 2 × 2 cube by a unit cube yields an instance of the indexing.

7 Conclusion

Locality-preserving indexing schemes are increasingly becoming a standard technique for devising simple and efficient algorithms for mesh-connected computers, for processing geometric data, for image processing, data structures, and several other fields. The methods developed here help to use the term “locality-preserving” in an accurate quantitative sense. This makes it possible to show that for the most important 2-D case, the newly presented H-indexing is superior with respect to locality compared to the previously used Hilbert indexing. We conjecture that H-indexings actually are optimal among all possible indexing schemes although we could only prove this for cyclic indexings yet. The claim holds for the Euclidean as well as the maximum as well as the Manhattan metric.

Our techniques for mechanically deriving upper bounds make it possible to quickly gain insight into the locality properties of indexing schemes. In particular, it was possible to give new, almost tight bounds for the 2-D Hilbert indexing with respect to the Euclidean metric and the maximum metric and also for the symmetric 3-D Hilbert indexings. In the following table we summarize our locality bounds for 2-D indexings:

d(i, j) (2-D)  Euclidean  maximum  Manhattan
General lower bound \sqrt{3.5|i − j|} − 1 \sqrt{3.5|i − j|} − 1 \sqrt{6.5|i − j|} − 2
Cyclic lower bound  \sqrt{4|i − j|} − 1  \sqrt{4|i − j|} − 1 \sqrt{8|i − j|} − 2
Upper bd. H-curve  \sqrt{4|i − j| − 2} \sqrt{4|i − j| + 4} − 1 \sqrt{8(|i − j| − 2)}
Upper bd. 2-D Hilbert  \sqrt{6.01|i − j|}  \sqrt{6.01|i − j|} \sqrt{9|i − j|} − 2

With the advent of 3-D mesh-connected computers like the Cray T3E, the increasing interest in processing 3-D geometrical data, and the growing importance of multidimensional data structures, locality-preserving 3-D mesh indexings will become more important.^{7} The following table summarizes locality bounds for 3-D indexings. In particular, it provides upper bounds for some symmetric 3-D variants of the Hilbert indexing. Note that here we still have a significant gap between upper and lower bounds.

6The program is available under http://liinwww.ira.uka.de/~sanders/hilbert/max3d.c.

7On modern parallel machines, good locality has mainly the indirect effect to increase the usable bandwidth whereas the latency due to the distance in the network is negligible compared to other overheads. So is would also be interesting to study bandwidth directly.

d(i, j) (3-D)  Euclidean  maximum  Manhattan
General lower bound  \sqrt[3]{11.1|i − j|} − \sqrt{3}  \sqrt[3]{8.25|i − j|} − 1 \sqrt[3]{42.625|i − j|} − 3
≈ 2.23\sqrt[3]{|i − j|} − \sqrt{3} ≈ 2.02\sqrt[3]{|i − j|} − 1 ≈ 3.49\sqrt[3]{|i − j|} − 3
Cyclic lower bound \sqrt[3]{12.39|i − j|} − \sqrt{3} \sqrt[3]{9|i − j|} − 1 \sqrt[3]{54|i − j|} − 3
≈ 2.31\sqrt[3]{|i − j|} − \sqrt{3} ≈ 2.08\sqrt[3]{|i − j|} − 1 ≈ 3.77\sqrt[3]{|i − j|} − 3
U. bd. 3-D Hil. (a)  \sqrt[3]{33.2|i − j|}  \sqrt[3]{29.2|i − j|}  \sqrt[3]{98.4|i − j|}
≈ 3.22\sqrt[3]{|i − j|}  ≈ 3.08\sqrt[3]{|i − j|}  ≈ 4.62\sqrt[3]{|i − j|}
U. bd. 3-D Hil. (b,c)  \sqrt[3]{34.2|i − j|}  \sqrt[3]{30.0|i − j|}  \sqrt[3]{112.1|i − j|}
≈ 3.25\sqrt[3]{|i − j|}  ≈ 3.11\sqrt[3]{|i − j|}  ≈ 4.83\sqrt[3]{|i − j|}

Future work

There are a number of interesting open questions, one is to close the gap between the upper and lower bound for non-cyclic 2-D indexings and, in particular, for 3-D indexings.

Mechanical inspection methods will play an important role for investigating other curves in particular for higher dimensions and for more complicated construction rules. The inspection methods themselves can be refined in various ways. They can be adapted to indexing schemes which are not based on combining cubic elements if we use a top-down decomposition rather than a bottom-up decomposition. For example, an H-indexing of size 2^{k} × 2^{k} could be partitioned into 2 · 4^{k′} triangles of area 2^{k−k′−1} without fixing k and for some constant k′. The construction principle for the H-curve then defines a (cyclic) path traversing all the triangles. Thus a computer can count the number of triangles on the (shortest) H-path between any two triangles. The algorithm can also be made faster by adaptively only refining those segments where computations for small k′ could not rule out high diameter segments.

Initial work concerning the study of structural and combinatorial properties of Hilbert indexings in higher dimensions have been started very recently [2]. In particular, it is clearly pointed out what characterizes an r-dimensional Hilbert curve for arbitrary r ≥ 2.

Acknowledgment We thank Henning Fernau for valuable pointers to the literature and Jochen Alber for helpful remarks concerning the notion of cyclic indexings and his clear presentation of some proofs using maximum metric [1].

References

[1] J. Alber. Locality properties of discrete space-filling curves: Results with relevance for computer science (in German). Studienarbeit, Universität Tübingen, Wilhelm-Schickard-Institut für Informatik, July 1997.

[2] J. Alber and R. Niedermeier. Hilbert indexings in arbitrary dimensions. Submitted for publication, August 1997.

[3] T. Asano, D. Ranjan, T. Roos, E. Welzl, and P. Widmayer. Space filling curves and their use in the design of geometric data structures. In R. Baeza-Yates, E. Goles, and P. V. Poblete, editors, Proceedings of the 2nd Symposium on Latin American Theoretical Informatics, number 911 in Lecture Notes in Computer Science, pages 36–48, Valparaíso, Chile, Apr. 1995. Springer-Verlag. To appear in TCS.

[4] E. Bugnion, T. Roos, R. Wattenhofer, and P. Widmayer. Space filling curves versus random walks. In M. v. Krefeld et al., editor, Algorithmic Foundations of GIS, LNCS. Springer, 1997. To appear.

[5] G. Chochia and M. Cole. Recursive 3D mesh indexing with improved locality. Technical report, University of Edinburgh, 1997. Short version appeared in the Proceedings of HPCN’97, LNCS 1225.

[6] G. Chochia, M. Cole, and T. Heywood. Implementing the Hierarchical PRAM on the 2D mesh: Analyses and experiments. In Symposium on Parallel and Distributed Processing, pages 587–595. IEEE Computer Science Press, October 1995.

[7] A. Dingle and I. H. Sudborough. Efficient mappings of pyramid networks. IEEE Transactions on Parallel and Distributed Systems, 5(10):1009–1017, 1994.

[8] C. Faloutsos and S. Roseman. Fractals for secondary key retrieval. In 8th ACM Symposium on Principles of Database Systems, pages 247–252, 1989.

[9] C. Gotsman and M. Lindenbaum. On the metric properties of discrete space-filling curves. IEEE Transactions on Image Processing, 5(5):794–797, May 1996.

[10] D. Hilbert. Über die stetige Abbildung einer Linie auf ein Flächenstück. Mathematische Annalen, 38:459–460, 1891.

[11] H. V. Jagadish. Linear clustering of objects with multiple attributes. ACM SIG-MOD Record, 19(2):332–342, June 1990.

[12] M. Kaddoura, C.-W. Ou, and S. Ranka. Partitioning unstructured computational graphs for nonuniform and adaptive environments. IEEE Parallel and Distributed Technology: Systems and Applications, 3(3):63–69, Fall 1995.

[13] C. Kaklamanis and G. Persiano. Branch-and-bound and backtrack search on mesh-connected arrays of processors. Mathematical Systems Theory, 27:471–489, 1994.

[14] M. Kunde, R. Niedermeier, K. Reinhardt, and P. Rossmanith. Optimal deterministic sorting and routing on grids and tori with diagonals. Technical Report TUM-I9629, Technische Universität München, Institut für Informatik, July 1996.

[15] M. Kunde, R. Niedermeier, and P. Rossmanith. Faster sorting and routing on grids with diagonals. In P. Enjalbert, E. W. Mayr, and K. W. Wagner, editors, Proceedings of the 11th Symposium on Theoretical Aspects of Computer Science, number 775 in Lecture Notes in Computer Science, pages 225–236. Springer-Verlag, 1994.

[16] R. Miller and Q. F. Stout. Mesh computer algorithms for computational geometry. IEEE Transactions on Computers, 38(3):321–340, March 1989.

[17] G. Mitchison and R. Durbin. Optimal numberings of an N × N array. SIAM J. Alg. Disc. Meth., 7(4):571–582, October 1986.

[18] R. Niedermeier. Towards Realistic and Simple Models of Parallel Computation. PhD thesis, Universität Tübingen, July 1996.

[19] A. Pérez, S. Kamata, and E. Kawaguchi. Peano scanning of arbitrary size images. In Int. Conf. on Patt. Recogn., pages 565–568, 1992.

[20] H. Sagan. Space-Filling Curves. Universitext. Springer-Verlag, 1994.

[21] P. Sanders and T. Hansch. Efficient massively parallel quicksort. In 4th International Symposium on Solving Irregularly Structured Problems in Parallel, number 1253 in Lecture Notes in Computer Science, pages 13–24. Springer-Verlag, June 1997.

[22] J. P. Singh. Parallel Hierarchical N-Body Methods and their Implications for Multiprocessors. PhD thesis, Stanford University, 1993.

[23] Q. F. Stout. Topological matching. In Proceedings of the 15th ACM Symposium on Theory of Computing, pages 24–31, 1983.

Figure 12: Relative positions of i (in A or B) and j (in C or D) yield the case distinction.

Appendix

A Proofs for exact results from Section 4, Theorem 1

Proof of Theorem 1, Manhattan case. We may focus attention on the smallest triangle containing both i and j. In Fig. 12 we have drawn the (smallest) triangle containing both i and j. It is easy to verify our claim for k ≤ 2 in Fig. 12. We perform an induction on k. Note that here we assume that both points on the two acute angles are part of the triangle, thus all triangles have size \frac{1}{2} · 4^{k} + 1. According to Fig. 12, we distinguish between six cases: A − B, A − C, A − D, B − C, B − D, and C − D, where X − Y means that i lies somewhere in X and j lies somewhere in Y.

We start with a simple case, namely B − C. We can easily observe that the worst case in this setting is when i and j are located at the two opposite acute angles e.g. of triangle C, thus reducing to the general case with k − 1.

Next we show the validness of our claim for the case A − D. We refine the case as shown in Fig. 13. Unfortunately, now we cannot at once exclude some of the occurring 16 subcases. Thus, in principle, we had to present a table with all 16 subcases. In what follows, however, we restrict attention to the subcase A.a − D.d, because for all other cases simple checking shows that d_{1}(i, j) ≤ \sqrt{8(|i − j| − 2)} trivially holds. As to A.a − D.d, we have d_{1}(i, j) ≤ 2 · 2^{k} − 2, |i − j| ≥ 14 · \frac{1}{2} · 4^{k−2} and thus \sqrt{8(|i − j| − 2)} = \sqrt{56 · 4^{k−2} − 16}, which doesn’t suffice to prove d_{1}(i, j) ≤ \sqrt{8(|i − j| − 2)}. Hence we further refine A.a−D.d as shown in Fig. 14. Now again by simple calculation it can be shown that except for the subcase A.aa − D.dd, all other cases fulfill our claim. Due to the self-similarity of H-curves we can refine subcase A.aa − D.dd in completely the same way as we did for for A.a − D.d. Iterating this process k − 2 times, we end up with the only “difficult”case A.a^{k−1} − D.d^{k−1}. Here we clearly have d_{1}(i, j) ≤ 2 · 2^{k} − 2 and |i − j| ≥ \frac{1}{2} · 4^{k} − 3. The relation

2 · 2^{k} − 2 ≤ \sqrt{8(\frac{1}{2} · 4^{k} − 3 − 2)} = \sqrt{4 · 4^{k} − 40}

is true for k ≥ 3, thus proving our claim.

Figure 13: Refinement of case A − D. Figure 14: Refinement of case A.a − D.d.

Figure 15: Refinement of case A − C.

Next we consider the case A − C, which we further refine as shown in Fig. 15. It suffices to study the subcases A.a − C.a, A.a − C.b, A.b − C.b, and A.d − C.a, because all other cases are clearly subsumed by these ones. We have the following table, which we directly obtain from considering Fig. 15.

\begin{matrix}Subcase & d_{1}(i, j) ≤ & |i − j| ≥ & \sqrt{8(|i − j| − 2)} ≥ \\ A.a − C.a & 5 · 2^{k−2} & 7 · \frac{1}{2} · 4^{k−2} & \sqrt{28 · 4^{k−2} − 16} \\ A.a − C.b & 6 · 2^{k−2} & 8 · \frac{1}{2} · 4^{k−2} & \sqrt{32 · 4^{k−2} − 16} \\ A.b − C.b & 5 · 2^{k−2} & 7 · \frac{1}{2} · 4^{k−2} & \sqrt{28 · 4^{k−2} − 16} \\ A.d − C.a & 4 · 2^{k−2} & 4 · \frac{1}{2} · 4^{k−2} + 2 & 4 · 2^{k−2} \end{matrix}

In fact, as to subcase A.d − C.a, there is one i such that |i − j| is only 4 · \frac{1}{2} · 4^{k−2} + 1. In this case, however, it holds that d_{1}(i, j) ≤ 4 · 2^{k−2} − 1, which is due to the construction principle of H-curves, see Subsection 4.1. The table reveals that for k > 2 in each subcase, except for A.a − C.b, our claim is fulfilled. In particular, subcase A.d − C.a also gives a worst case situation providing the lower bound. As to A.a − C.b, we just mention in pass that a further refinement analogous to case A.a − D.d before (leading to 16 subcases) shows the validity of our claim. We omit the messy but straightforward details. Note, however, that by way of contrast to A.a − D.d we do not even need to “iterate” here.

The case B − D is similar to A − C. According to Fig. 16 it suffices to study the subcases B.c − D.a, B.c − D.c, B.c − D.d, B.d − D.a, and B.d − D.d, because all the other cases are subsumed by these ones. We have the following table.

\begin{matrix}Subcase & d_{1}(i, j) ≤ & |i − j| ≥ & \sqrt{8(|i − j| − 2)} ≥ \\ B.c − D.a & 4 · 2^{k−2} & 5 · \frac{1}{2} · 4^{k−2} & \sqrt{20 · 4^{k−2} − 16} \\ B.c − D.c & 5 · 2^{k−2} & 7 · \frac{1}{2} · 4^{k−2} & \sqrt{28 · 4^{k−2} − 16} \\ B.c − D.d & 6 · 2^{k−2} − 2 & 8 · \frac{1}{2} · 4^{k−2} & \sqrt{32 · 4^{k−2} − 16} \\ B.d − D.a & 4 · 2^{k−2} − 1 & 4 · \frac{1}{2} · 4^{k−2} & \sqrt{16 · 4^{k−2} − 8} \\ B.d − D.d & 5 · 2^{k−2} & 7 · \frac{1}{2} · 4^{k−2} & \sqrt{28 · 4^{k−2} − 16} \end{matrix}

Figure 16: Refinement of case B − D.

Figure 17: Refinement of case C − D.

The validity of our claim for case B.c − D.d now follows in complete analogy to case A.a − C.b before. As to case B.d − D.a, the claim is true if k ≥ 3, thus providing the validity of our claim for case B − D.

It remains to prove our claim for the cases A − B and C − D. The same proof applies for both. Consider Fig. 17, giving a refined view of C − D. Calculating a table for all 16 subcases as we did before in other subcases, it comes out that the “difficult cases” are C.a − D.a and C.b − D.a and the corresponding symmetric ones (i.e., C.d − D.d and C.d − D.c), which have to be further refined (as we already did in Fig. 17). Again considering the subcases of C.a − D.a and C.b − D.a, it turns out that d_{1}(i, j) ≤ \sqrt{8(|i − j| − 2)} is fulfilled (assuming k ≥ 3) except for the case C.aa − D.aa. Making use of the self-similarity of the H-curve, it follows that after k − 1 iterations of refinement we end up with the only “difficult” case C.a^{k−1} − D.a^{k−1}. Here we have d_{1}(i, j) ≤ 2 · 2^{k} − 1 and |i − j| ≥ \frac{1}{2} · 4^{k}, yielding the validity of our claim.

Proof of Theorem 1, Euclidean case. We consider the triangles of size 2^{2l−1}, l ≥ 1 according to the construction scheme of H-curves. Note that in order to get common

2^{l} \{ r sp  u v p_{A} p_{B}  p_{C} p_{D} x y z • • • • • • • •  • • • • • • • • \overline{•} \overline{•}  \overline{•} •  • \overline{•}  \overline{•} •  • \overline{•}  \overline{•} •  • \overline{•}  \overline{•} •  • \overline{•}  \overline{•}  \overline{•}  \overline{•} •  •  •  • \overline{•}  \overline{•}  \overline{•}  \overline{•} •  •  •  • • A B  C  D  For l = 1 we have 2^{l} \{ r sp u v

Figure 18: A triangle of size 2^{2l−1} + 3, including the additional points r, u and v.

points for the connection of the triangles, we assume that the points r, u, and v (see Fig. 18) also belong to the triangle. To get a 2^{k} ×2^{k} mesh, we simply restrict the triangle for l = k + 1 to B ∪ C in Fig. 18. (Because of symmetry, we can use the connection at y.) To prove our result we employ an induction on the size of the triangles. As Fig. 18 shows, we extend the scope by three additional points: r, v and for technical reasons we assume a further artificial connection to the point u from a point diagonally under u. (This means u replaces the point left of u.)

We start with the base of the induction for l = 1 (see Fig. 18), where we have |i − j| ≤ 3. In this case d(i, j) ≤ \sqrt{4|i − j| − 2} ≤ \sqrt{10} is always fulfilled.

Now we come to the induction step, assuming that l ≥ 2. We distinguish between subcases X − Y, which means that i lies somewhere in X and j lies somewhere in Y. Clearly, cases A − A, B − B, C − C, and D − D follow easily from the induction hypothesis.

In the case C − D, we distinguish between two further subcases. First assume that not both i and j (where w.l.o.g. i shall be in C and j in D) are located exactly at the corresponding diagonal lines. This means that either the angle between the lines from i to y and from y to j (cf. Fig. 18) or the angle between the lines from i to z and from z to j is at most 90^{o}. Thus we may use the estimation d(i, j) ≤ \sqrt{d^{2}(i, y) + d^{2}(y, j)} and applying the induction hypothesis for d(i, y) and d(y, j), we obtain

d(i, j) ≤ \sqrt{4|i − y| − 2 + 4|y − j| − 2} = \sqrt{4|i − j| − 4}.

Thus our claim is verified (analogously for z).

If both i and j are lying on the two diagonal lines as drawn in Fig. 19, then we get the following. W.l.o.g. assume that y_{j} ≥ y_{i}. Then

d(i, j) = \sqrt{(y_{i} + y_{j} − 1)^{2} + (y_{j} − y_{i})^{2}} = \sqrt{2y_{i}^{2} + 2y_{j}^{2} − 2y_{i} − 2y_{j} + 1}.

Figure 19: The case when i and j are lying both on opposite diagonal lines. Note that every second row contains such a point. The number of rows till i and j, respectively, counting from the top are denoted y_{i} and y_{j}, respectively.

On the other hand,

|i − j| ≥ \frac{1}{2}(y_{i} + 1)^{2} − 1 + \frac{1}{2}(y_{j} + 1)^{2} − 1 − 1 = \frac{1}{2}y_{i}^{2} + \frac{1}{2}y_{j}^{2} + y_{i} + y_{j} − 2

due to the construction principle of H-curves and some straightforward considerations, yielding the validity of our claim in the case C − D.

The case A − B is a bit more tricky. In order to employ a similar argument as for C − D, we artificially regard x and y as the connection of A and B (see Fig. 18). It is obvious that the Euclidean distance from any point within the triangle to x or y is at least as big as the Euclidean distance to the real points of connection. Thus in a sense we only make things “worse” and are finished if we can upper bound d(i, j) using x or y. Now we can again distinguish two subcases in the same way as in case C −D: If not both i and j are located at diagonal lines, then completely the same argumentation as in C − D applies. If both i and j are on diagonal lines, then analogous considerations as for C −D show that d(i, j) ≤ \sqrt{2y_{i}^{2} + 2y_{j}^{2} − 2y_{i} − 2y_{j} + 1} and |i−j| ≥ \frac{1}{2}y_{i}^{2} + \frac{1}{2}y_{j} −1, which implies our claim for y_{i}, y_{j} ≥ 2, which always holds.

It remains to handle cases (A ∪ B) − (C ∪ D). For i ∈ A ∪ B we distinguish the case i ≠ r, where we use the induction hypothesis for d(i, p), from the case i = r, where we use |r − p| = 4^{l−1}. For j ∈ C ∪ D we distinguish the case j ≠ v and u is reached by the normal way (i.e., not using the artificial diagonal connection), where we use the induction hypothesis for d(p, j), the case j = v, where we use |p − v| = 4^{l−1} + 1 and the case j = u being reached on the artificial way, where we use |p − u| = 4^{l−1}. In each of those 6 combined cases we make an estimation using an angle of at most 90^{o} at p or a point beside p. Simple calculations yield

d(i, j) ≤  \sqrt{d(i, p)^{2} + d(p, j)^{2}}  ≤ \sqrt{4|i − j| − 4}
d(r, j) ≤ \sqrt{(2^{l} − 1)^{2} + (d(p, j) + 1)^{2}} ≤ \sqrt{4|r − j| − 2(2^{l} − d(p, j))}
d(i, v) ≤ \sqrt{(d(p, i) + 1)^{2} + (2^{l} − 1)^{2}} ≤ \sqrt{4|i − v| − 2(2 + 2^{l} − d(p, i))}
d(r, v) ≤  \sqrt{(2^{l})^{2} + (2^{l})^{2}}  ≤ \sqrt{4|r − v| − 4}
d(i, u) ≤ \sqrt{(d(p, i)^{2} + (2^{l} − 1)^{2}} ≤ \sqrt{4|p − u| − 1 − 2 · 2^{l}}
d(r, u) ≤  \sqrt{(2^{l})^{2} + (2^{l} − 1)^{2}}  ≤ \sqrt{4|r − u| − 2 · 2^{l} + 1}

and the claim follows for l ≥ 1 in each case.

Proof of Theorem 1, maximum case. The proof can be done similar to the Manhattan case. It has been part of a semester work by Alber [1].

B Details of Subsection 5.3

In what follows we want to substantiate our claim that surjectivity is necessary for Theorem 4 (maximum case) and Theorem 6. Note, however, that the following is in no way a formal proof.

A non-orthogonal subsquare of an n×n-square with n = 4(a+b)m having the form

can be filled by using parts of the form ^{4a 2b-1 2b}corresponding to one

node of the H-curve filling an m × m-square. Each of these parts is filled by a curve leading from one corner to another, which may look for example for a = 1 and b = 4 as follows:

} 4a
} 2b − 1

} 2b

Connecting them leads, for example for m = 4, to such a partial filling of a n × n square with n = m4(a + b) as indicated in Fig. 20.

In this way for any natural numbers a, b, a family of such curves can be generated. Some of them, for example, a = 3, b = 1 (or a = 5, b = 3) again hit a worst case on the diagonal (see Fig. 21; also cf. Subsection 4.1 and Figure 4 there) where the Manhattan metric is \sqrt{2} times the Euclidean metric. Here having combined two triangles of different size, we get |i − j| ≈ 5\sqrt{(n/4)^{2} + (n/8)^{2}}^{2}/2 = n^{2}25/128 and d_{1}(i, j) ≈ n5/4 = \sqrt{n^{2}25/16} ≈ \sqrt{8|i − j|} (or |i − j| ≈ 17\sqrt{(n/8)^{2} + (n/32)^{2}}^{2}/2 = n^{2}289/2048 and d_{1}(i, j) ≈ n17/16 = \sqrt{n^{2}289/256} ≈ \sqrt{8|i − j|}).

But some others do not hit a worst case on the diagonal: If we approximate a/b to \sqrt{2} − 1, which leads to an angle of α = 45^{o}/2 = 22.5^{o}, then m4a ≈ n\sqrt{1/2} and

\begin{matrix}\} m4a \\ \} m4b − 1 \end{matrix}

Figure 20: A partial filling of an n × n-square with n = m4(a + b) and m = 4.

i •  j •  } 3n/4 } n/4 α ^{i •  j •  } 5n/8 } 3n/8 α}

Figure 21: Two ways (a = 3, b = 1 and a = 5, b = 3) of combining two triangles of different size. Observe that the line from i to j is a 45^{o}-diagonal and α = 18.43^{o} in the left picture and α = 30.96^{o} in the right picture. In addition, note that in the left picture j is in the middle of one side of the non-orthogonal square and in the right picture j divides the side in 1/4 and 3/4.

m4b ≈ n(1 − \sqrt{1/2}) and we get asymptotically |i − j| ≈ (n\sqrt{2 − \sqrt{2}})^{2}5/16 = n^{2}(2 − \sqrt{2})5/16 = 0.183n^{2} and

d_{1}(i, j) ≈ n(1/2 + \sqrt{1/2}) = \sqrt{n^{2}(3/4 + \sqrt{1/2})} ≈ \sqrt{7.96|i − j|}

(or |i − j| ≈ (n\sqrt{2 − \sqrt{2}})^{2}17/64 = n^{2}(2 − \sqrt{2})17/64 = 0.155n^{2} and d_{1}(i, j) ≈ n(3/4 + \sqrt{1/2}/2) = \sqrt{n^{2}1.22} ≈ \sqrt{7.83|i − j|}). This means that it leads asymptotically to a factor of \sqrt{7.96} for the Manhattan metric and accordingly to \sqrt{3.92} for maximum metric, if we approximate a/b to \sqrt{2} − 1.