arXiv:1710.03435v2 [math.CO] 16 Jan 2018

Combinatorial and Asymptotical Results on
the Neighborhood Grid
Martin Skrodzki, Ulrich Reitebuch, and Konrad Polthier
martin.skrodzki@fu-berlin.de, ullrich.reitebuch@fu-berlin.de,
konrad.polthier@fu-berlin.de

Berlin, January 18, 2018
Abstract
In 2009, Joselli et al introduced the Neighborhood Grid data structure for fast computation of neighborhood estimates in point clouds.
Even though the data structure has been used in several applications
and shown to be practically relevant, it is theoretically not yet well
understood. The purpose of this paper is to present a polynomial-time
algorithm to build the data structure. Furthermore, it is investigated
whether the presented algorithm is optimal. This investigations leads
to several combinatorial questions for which partial results are given.

1

Introduction

The neighborhood grid data structure can be used to compute estimates of
neighborhoods in point sets. It has been introduced by Joselli et al. [1],
[2]. In order to give a short introduction to the data structure, consider the
example in Figure 1. It shows how points from a point cloud (Figure 1a)
are placed in a grid (Figure 1b). The order in which the points are given is
random, thus their initial placement in the grid is also. After the placement,
only the coordinates of the points are considered in the grid (Figure 1c).
The grid as obtained in Figure 1c will now be sorted. Each row should grow
in the first coordinates from left to right, each column should grow in the
second coordinates from bottom to top. A corresponding sorted grid is given
in Figure 2a. Note how it, in this example, recovers the combinatorial neighborhood relation from the points.

1

1 Introduction

8.23, 4.79 8.41, 1.96 1.53, 1.30

2.06, 7.76 1.77, 5.46 9.18, 9.05

4.07, 5.13 3.73, 6.84 4.27, 1.45

(a) Point cloud with
nine points in R2 .

(b) The points are initially placed randomly.

(c) The point coordinates are considered.

Figure 1: First part of the neighborhood grid pipeline.

2.06, 7.76 3.73, 6.84 9.18, 9.05

2.06, 7.76 3.73, 6.84 9.18, 9.05

1.77, 5.46 4.07, 5.13 8.23, 4.79

1.77, 5.46 4.07, 5.13 8.23, 4.79

1.53, 1.30 4.27, 1.45 8.41, 1.96

1.53, 1.30 4.27, 1.45 8.41, 1.96

(b) Determining the neighbors
of the upper left point by looking at its neighbors in the grid.

(a) Coordinates are sorted to
grow in columns and rows.

Figure 2: Second part of the neighborhood grid pipeline.
In order to use the neighborhood grid to determine a neighborhood estimate
for a given point, find that point in the sorted grid. Then, consider a small
neighborhood around that point, e.g. the one-ring around it. The size of this
neighborhood should not depend on the number of inserted points such that
this lookup runs in constant time (asymptotically). From that neighborhood,
find the closest point to the considered point and output it as estimated
nearest neighbor.
In this report, we collect new results on the neighborhood grid data structure.
Malheiros and Walter [3] investigated several iterative building strategies for
the data structure. Despite the evidences of practical relevance, as given in
the publication cited above, neither Joselli nor Malheiros investigated the

2

2 The Neighborhood Grid

asymptotic building times of the grid or answered the question for a timeoptimal building algorithm. Therefore, this paper contains:
• a polynomial-time algorithm to build a neighborhood grid (Theorem 1,
page 5),
• combinatorial results on the number of possible sorted placements (Theorem 2, 7),
• a complete list of unique sorted placements for n ∈ {1, 2, 3} (Section
3.5),
• a proof of non-existence of unique sorted placements for n ≥ 4 (Section
3.5).
So far, some questions remain unanswered:
• Is the presented algorithm time-optimal?
• For a given n ∈ N, n ≥ 4, what is a point configuration with the least
or largest number of stable states?
For the case of the latter question we present a conjecture, see page 16.

2

The Neighborhood Grid

In this first section, we present the neighborhood data structure, fix corresponding notation, and prove a first theorem on a polynomial-time building
algorithm.

2.1

Definition of the Data Structure

Given a set of points P = {p1 , . . . , pN | pi ∈ Rd }. In the following we will
assume that N = n2 for some n ∈ N and d = 2. Therefore each point is given
by pi = (pi1 , pi2 ) ∈ R2 , where pi1 will be referred to as x- and pi2 as y-value.
Furthermore, we assume that pi 6= pj for all i 6= j. Consider Section 4 for
the general case without these restrictions. Finally, we can restrict w.l.o.g.
to pi ∈ N2 for all i ∈ [N ], see Section 3.1 for an explanation of this restriction.
The points will be placed in an n × n matrix, where each cell of the matrix
contains a point pi . That is, we consider a matrix M ∈ (R2 )n×n which then
has the form

3

2.2 Polynomial-Time building algorithm

(a1n , b1n ) . . . (ann , bnn )
..
..
.
.
M=
..
.
.
(a11 , b11 ) . . . (an1 , bn1 )

(1)

Ultimately, we want to order the points in the matrix such that the following
state is reached.

Definition 1. The matrix M as given in (1) is said to be in a stable state
if and only if the following two conditions are satisfied for any i, j ∈ [n],
i 6= j.
1. For all k ∈ [n] it is: i < j ⇒ aki < akj ∨ (aki = akj ∧ bki < bkj ).
2. For all ` ∈ [n] it is: i < j ⇒ bi` < bj` ∨ (bi` = bj` ∧ ai` < aj` )

In other words, a matrix M is in a stable state, if the points in each row of
M are ordered lexicographically according to the first and then the second
coordinate. Similarly, all columns of M have to be ordered lexicographically
according to the second and then the first coordinate. An illustration of
Definition 1 is given in Figure 3. We call a stable state unique, if there
exists no other stable state for the same point configuration P .

2.2

Polynomial-Time building algorithm

Now the following question arises naturally. For any set of points P as
specified above, is there a bijective placement π : [n2 ] → [n] × [n], i 7→ (k, `)
such that the matrix Mπ (P ) with
(pπ−1 (n,1)1 , pπ−1 (n,1)2 ) . . . (pπ−1 (n,n)1 , pπ−1 (n,n)2 )
..
..
.
.
M=
..
.
.
(pπ−1 (1,1)1 , pπ−1 (1,1)2 ) . . . (pπ−1 (1,n)1 , pπ−1 (1,n)2 )

(2)

is in a stable state. In other words, given n2 points, can these be written into
an n × n matrix s.t. it is in a stable state as defined in Definition 1.

4

2.2 Polynomial-Time building algorithm

(55, 42)

(60, 49)

(26, 61)

(95, 13)

(13, 69)

(95, 65)

(06, 69)

(26, 61)

(86, 89)

(02, 55)

(80, 34)

(86, 41)

(05, 19)

(47, 11)

(95, 13)

Figure 3: On the left three cases where two marked in green satisfy the first
condition of Definition 1, while the red case violates it. On the right a 3 × 3
matrix M in stable state.

Theorem 1. For every set of points P = {p1 , . . . , pN | pi ∈ R2 } there is a
bijective placement π such that Mπ (P ) is in a stable state. A placement π
can be found in O(N log(N )).

Proof. Consider the points p1 , . . . , pN as a sequence. Sort this sequence according to the first condition given in Definition 1. Obtain a sequence
(q11 , q12 ), (q21 , q22 ), . . . , (qN 1 , qN 2 ),
where for i, j ∈ [n], i < j we have qi1 < qj1 or (qi1 = qj1 ∧ qi2 < qj2 ). Now
split this sequence into n blocks as follows:
(q11 , q12 ), . . . , (qn1 , qn2 ), (q(n+1)1 , q(n+1)2 ), . . . , (q(2n)1 , q(2n)2 ),
{z
} |
|
{z
}
=:Q1

=:Q2

. . . (q(n2 −n+1)1 , q(n2 −n+1)2 ), . . . , (qN 1 , qN 2 ), .
|
{z
}
=:Qn

Now consider each sequence Qi and sort it according to the second condition
given in Definition 1. Obtain a sequence
Rk := (r11 , r12 ), (r21 , r22 ), . . . , (rn1 , rn2 ), k ∈ [n],
5

2.2 Polynomial-Time building algorithm

where for i < j we have ri2 < rj2 or (ri2 = rj2 ∧ ri1 < rj1 ). That is, the
points in the sequence Rk are sorted according to the second condition of
Definition 1. Furthermore, for i < j, any point from Ri satisfies the first
condition of Definition 1 when compared to any point from Rj , since the Rk
derive from the Qk . Therefore, placing the sequence Rk into the kth column
of the matrix M results in a stable state.
Concerning the runtime, in the first step, N points were sorted, which takes
O(N log(N )). In the second step, √
n sets of n points each were sorted, which
takes n · O(n log(n)) = O(n2 log( N )) = O(N log(N )). Hence, the stable
state was computed in O(N log(N )).
An illustration of the procedure presented by this theorem is given in Figure 4.
{(26, 61), (06, 69), (95, 13), (86, 41), (05, 19), (02, 55), (86, 89), (47, 11), (80, 34)}
↓ Consider all points as one sequence. ↓
(26, 61) (06, 69) (95, 13) (86, 41) (05, 19) (02, 55) (86, 89) (47, 11) (80, 34)

↓ Sort the sequence according to the first condition of Definition 1. ↓
(02, 55) (05, 19) (06, 69) (26, 61) (47, 11) (80, 34) (86, 41) (86, 89) (95, 13)

↓ Separate into chunks of size n and sort them according to the second
condition of Definition 1. ↓
(06, 69)

(26, 61)

(86, 89)

(02, 55)

(80, 34)

(86, 41)

(05, 19)

(47, 11)

(95, 13)

Figure 4: An illustration of the algorithm outlined in Theorem 1. The last
step gives the rows of the final matrix which is then in a stable state.
Theorem 1 imposes an upper bound on the runtime of any time-optimal
comparison-based algorithm that creates a stable state of a matrix M . The
next question is then: What is a lower bound? A trivial lower bound is given
by the number of points in the matrix, N . In the next section, we investigate
whether this lower bound can be raised to N log(N ).
6

3 Combinatorial Results

3

Combinatorial Results

In order to better understand the search space for any sorting algorithm that
is to build a stable state of a matrix M , we start by counting the number of
possible stable states and giving two necessary conditions on their uniqueness.
Then, we proceed to give a list of all point configurations P for n ∈ {1, 2, 3}
that omit to a single, unique stable state. As a last part of this section, we
investigate which point configuration has the largest number of stable states.

3.1

Counting Stable States and a lower Bound

Concerning the stable state of a matrix, it is not important what actual x- or
y-values the points have, but only how these values compare to each other.
Therefore, the setup can be simplified by fixing the x and y values on the set
[N ]. In terms of the pi the restriction is
{p11 , . . . , pN 1 } = {p12 , . . . , pN 2 } = {1, . . . , N }.

(3)

In this restricted set we can quantify several of the occurring states.

Theorem 2. Given some N, n ∈ N with N = n2 , there are:
1. (n2 )! possible point sets P and ((n2 )!)2 ways to fill the matrix,
2. ((n2 )!/(n!)n )2 ways to fill the matrix with a stable state,
3. 1/(n!)2n of all fillings of the matrix are stable.

Proof. Concerning the first statement, when building the points pi , iterate
through the x-values. For each x-value pick one of the y-values from [N ] not
picked yet. Then for x = 1, there are N choices, for x = 2, there are N − 1
choices, etc. Hence there are N ! possible point sets. Each pi of the point set
P occupies one of the N points in the matrix, therefore, there are N ! ways
to write each point set into the matrix. Therefore, there are (N !)2 possible
ways to fill the matrix.
Concerning the second statement, a matrix is in a stable state if both conditions of Definition 1 are met. Because of the restriction given by (3), the
equality case is never met in either condition of Definition 1. Therefore, for
each condition, it suffices to check the x- or y-values respectively, neglecting
the other. When setting up the x-values for the first row, one can pick n of
7

3.2 Uniqueness of Stable States

the possible N values, which then admit to a unique order. Therefore, for
2
the x-values in the first row, there are nn possibilities. For the second row,


2
2
there are n n−n possibilities, until there is n −(n−1)n
= 1 possibility for the
n
last row. Overall, there are
(n−1)  2
Y
k=0


(n2 − n)!
(2n)! n!
(n2 )!
n − kn
n2 !
· 2
· ... ·
·
=
= 2
(n − n)!n! (n − 2n)!n!
n!n! n!
(n!)n
n

possibilities to put x-values into the matrix and obtain a stable state from
(n2 )!
them. Accordingly, there are (n!)
n ways to write y-values into the matrix and
obtain a stable state. Hence, overall, there are
 2 2
(n )!
(n!)n
stable states.
Finally, because of the first two results, the fraction of stable fillings amongst
all fillings of the matrix are
 2 2
(n )!
(n!)n
1
=
.
2
2
((n )!)
(n!)2n

3.2

Uniqueness of Stable States

In the previous section it was shown that the running time of the algorithm
outlined in Theorem 1 gives an upper bound on the sorting problem. To
prove a lower bound, we assume the following.

Assumption 1. Given some n ∈ N, assume that there is a set P of points
p1 , . . . , pN such that there exists a unique stable state for P .

Given that assumption, optimality of the Algorithm of Theorem 1 follows by
the following argument:
Proof. Given an n ∈ N and the set of points P assumed to exist. Then the
unique stable state in particular satisfies the first condition of Definition 1
for every row. Therefore, the algorithm needs to sort every row, which takes
8

3.2 Uniqueness of Stable States

O(n log(n)) time for each row, that is n · O(n log(n)) = O(N log(N )) time
in total. Hence, given Assumption 1, O(N log(N )) is a lower bound on the
computation of a stable state.
Note that the assumption of the existence of a unique stable state is crucial
in this argument. If the assumption was proven to be wrong, the algorithm
can pick any stable state to create a sorting of the rows there, which could
lead to a faster than O(N log(N )) algorithm because of the larger search
space.
Concerning Assumption 1, it is not at all obvious that for a given point configuration, there has to be a unique stable state. Three point configurations
are given in Figure 5, where two have a unique stable state, while the other
one has two stable states. The uniqueness of the stable state of the 2 × 2
matrix shown follows by this reasoning: The element (1, 1) has to be placed
in the upper left corner, since it has x-, as well as lowest y-value compared to
all other elements. The element (2, 4) has largest y-value, therefore it needs
to be placed in the lower row. But it also has second lowest x-value, therefore
it has to be placed in the lower left or upper right corner. Taken these two
arguments together, the element has to be placed in the lower left corner.
Finally, the shown configuration is the only way to complete the matrix to a
stable state.
(3, 7) (4, 8) (9, 9)
(2, 4) (3, 3)

(2, 2) (4, 4)

(3, 3) (4, 4)

(2, 6) (5, 5) (8, 4)

(1, 1) (4, 2)

(1, 1) (3, 3)

(1, 1) (2, 2)

(1, 1) (6, 2) (7, 3)

Figure 5: On the left a point configuration with n = 2 which has a unique
stable state. In the middle a point configuration with n = 2 with its two
possible stable states. On the right a point configuration with n = 3 which
has a unique stable state.
The examples from Figure 5 pose two further questions:
1. Is there a unique stable state for every n ∈ N?
2. Can we classify all unique stable states?

9

3.3 First Necessary Condition on Stable States

3.3

First Necessary Condition on Stable States

For a necessary condition on the uniqueness of a stable state reconsider the
algorithm outlined in Theorem 1. Note that the n smallest x-values are
placed in the first column, the n second-smallest x-values are placed in the
second column, etc. Finally, a stable state is obtained from this procedure.
Furthermore, the algorithm can be run the other way around, placing the
n smallest y-values in the first row, the n second-smallest y values in the
second row, and so on to reach a stable state. In the following, we will call
these two conditions x-bin and y-bin condition.
Assume now that a stable state is given, which violates the x-, the y-, or both
bin conditions. Then applying the algorithm from Theorem 1 with sorting
according to the violated bin condition gives another stable state for the
same points. This observation establishes the following necessary condition
for the uniqueness of a stable state.

Theorem 3. Given a matrix m in stable state. If the stable state is unique,
then both the x- and the y-bin condition hold.

Note that Theorem 3 does not give an equivalence. Consider the point configuration P = {(1, 1), (2, 3), (3, 2), (4, 4)}. A stable state of this configuration
satisfying both x- and y-bin condition is shown on the left side of Figure 6.
However, the point configuration admits to a second stable state, shown on
the right side of Figure 6. This showcases that x- and y-bin condition are
only necessary, but not sufficient conditions.
(2, 3) (4, 4)

(3, 2) (4, 4)

(1, 1) (3, 2)

(1, 1) (2, 3)

Figure 6: On the left hand side a configuration in stable state, satisfying
both x- and y-bin condition. On the right a stable state of the same configuration P , showing that x- and y-bin condition do not imply uniqueness.
Theorem 2 already tells us that there are (n2 )!/(n!)n ways to put x-values
into the matrix such that they form a stable state. Furthermore, there are
(n2 )! possible ways to fill the matrix with x-values. How many of these satisfy
the condition of Theorem 3.
10

3.4 Second Necessary Condition on Stable States

Theorem 4. There are (n!)2n stable states that satisfy both the x- and the
y-bin condition.

Proof. Assume the x- and y-bin condition holds, then the first row contains
the n smallest y-values, while the first column contains the n smallest xvalues. Either values can be permuted arbitrarily without destroying the
stable state. This holds for every row and every column. Therefore, there
are (n!)n ways to reorganize the rows and similarly (n!)n ways to reorganize
the columns and still obtain a stable state. Hence, (n!)2n stable states satisfy
both bin conditions.
The situation established in Theorems 2 and 4 can be visualized as in Figure 7.



(n!)n


(n2 )!/(n!)n − (n!)n 
(n2 )! − (n2 )!/(n!)n

(n!)n

(n2 )!/(n!)n − (n!)n

(n2 )! − (n2 )!/(n!)n

stable x − y − bin

stable x − bin

not stable



stable y − bin

stable

not stable




not stable

not stable

not stable

Figure 7: Distribution of possibly unique stable states amongst all stable
states and amongst all states.
However, we can derive even more from the algorithm of Theorem 1.

3.4

Second Necessary Condition on Stable States

Given the terminology and results from Section 3.3, we can derive an even
stronger necessary condition for unique stable states. Namely, the following
holds:

Theorem 5. Given an n × n matrix m in stable state. If the stable state
is unique, then any k × k submatrix of m with k ∈ [n] is in a unique stable
state.

Proof. Given some n × n matrix m in a unique stable state. Assume there
exists some k × k submatrix m̃ of m, k ∈ [n], such that m̃ is not unique, but
11

3.5 Enumeration of all unique Stable States

has a different stable state m̄. Assume that m̃ occupies rows r, . . . , r +(k −1)
and columns c, . . . , c + (k − 1) in m.
Because of the first necessary condition on stable states (Section 3.3) we know
that the x-values of any elements in columns 1, . . . , c − 1 are smaller and the
x-values of any elements in the columns c + k, . . . , n are larger than all xvalues in m̃ respectively. This remains true independent of any reordering, in
particular for m̄. The same argument holds for the y-values in rows 1, . . . , r −
1 and the y-values in rows r + k, . . . , n when compared with the y-values of
m̃.
Therefore, replacing m̃ by m̄ in m gives another stable state, which violates
the uniqueness of m.

3.5

Enumeration of all unique Stable States

The number of unique stable states for any n ∈ N is given in Table 1. All
unique stable states for n = 2 and n = 3 are shown in Figures 8 and 9 respectively. Brute-Force computation shows that none of the 37, 536 possible 4 × 4
point configurations satisfying the second necessary condition from Section
3.4 is uniquely stable. That is, Assumption 1 does not hold. Furthermore,
from n = 4 upward, there can never again be any uniquely stable point configuration, as if there was one, it would have to include a unique stable 4 × 4
state, which does not exist.
n # stable states
1
1
12
2
3
966
≥4
0
Table 1: Number of unique stable states for n × n matrices.

Figure 8: All 12 unique 2 × 2 stable states. Red edges correspond to
horizontal neighborhood relation in the grid, while blue edges indicate a
vertical neighborhood relation in the grid.

12

3.5 Enumeration of all unique Stable States

13
Figure 9: All 966 unique 3 × 3 stable states.

3.6 The worst Stable State

The fact that for n ≥ 4 there is no point configuration with a single unique
stable state, it raises the following question:

Open 1. Given n ∈ N, n ≥ 4, what is a point configuration P with the
minimum number of stable states among any point configuration with n2
points?

3.6

The worst Stable State

We proceed by turning the question from the last paragraph around. What
is the maximal number of stable states a point configuration can obtain for
some given n ∈ N? In order to investigate this question, we first turn to
a specific point configuration, for which we can count the number of stable
states. Consider the ”identity”: {(1, 1), (2, 2), . . . , (n2 , n2 )}. Counting the
number of stable states for the identity is equivalent to placing only one
number in each field of the n × n matrix, which then has to satisfy both
conditions of Definition 1.
In order to count the number of stable states for the identity, we introduce
the concept of Ferrers Diagrams and Young tableaux. Taken from [4].

Definition 2. Let λ = (λ1 , λ2 , . . . , λ` ) be a partition of N . The Ferrers
diagram of λ is an array of N cells having ` left-justified rows with row i
containing λi cells for 1 ≤ i ≤ `.

Consider for example N = 4. Then N can be partitioned in five different
ways:
4

=3+1

=2+2

=2+1+1

= 1 + 1 + 1 + 1,

as illustrated in Figure 10.

Definition 3. Let λ = (λ1 , λ2 , . . . , λ` ) be a partition of N . A Young tableau
of shape λ is an array t obtained by filling the cells of the Ferrers diagram of
λ with the numbers 1, 2, . . . , N bijectively.
A tableau t is standard if the rows and columns of t are increasing sequences.

14

3.6 The worst Stable State

Figure 10: The five possible Ferrers diagrams for the partitions of N = 4
given by λ = (4), λ = (3, 1), λ = (2, 2), λ = (2, 1, 1) and λ = (1, 1, 1, 1).
1 2 3
4

4 1 3
2

Figure 11: Two Young tableaus corresponding to the partition λ = (3, 1)
of N = 4. The left tableau is standard, while the right one is not.
Clearly, the number of standard Young tableaux of shape λ = (n, . . . , n) for
N = n2 is equal to the number of stable states for the identity. Denote by
f λ the number of standard λ-tableaux. In order to compute it, we introduce
the concept of hooks.

Definition 4. If v = (i, j) is a node in the diagram of λ, then it has hook
Hv = Hi,j = {(i, j 0 ) | j 0 > j} ∪ {(i0 , j) | i0 ≥ i}
with corresponding hooklength
hv = hi,j = |Hi,j |.

Figure 12: Given the partition λ = (5, 4, 3, 3, 1) of N = 16, the dots show
the hook H2,2 with a hook length of h2,2 = 5.
It is now easy to state the hook formula of Frame, Robinson, and Thrall.
15

3.6 The worst Stable State

Theorem 6. Let λ = (λ1 , . . . , λ` ) be a partition of N . Then
fλ = Q

N!
(i,j)∈λ

hi,j

.

In the concrete case of the identity, where N = n2 , λ = (n, . . . , n), we have
hi,j = n − i + n − j + 1 = 2n − i − j + 1.
Therefore, the number of stable states of the identity is given by
N!
.
j=1 (2n − i − j + 1)

f (n,...,n) = Qn Qn
i=1

(4)

The results for n ∈ {1, 2, 3} and computational experiments lead us to state
the following conjecture.

Conjecture 1. Given n ∈ N, the number of stable states of any point configuration P on n2 points is less or equal to f (n,...,n) .

If the number of stable states of any point configuration is indeed bounded
from above by f (n,...,n) , then the running time of any decision-based algorithm
is bounded from below

log

n2 !
f (n,...,n)



n Y
n
Y
= log
(2n − i − j + 1)

=

!

i=1 j=1
n
n
XX

log(2n − i − j + 1)

i=1 j=1

= n · log(n) +

n
X

(i · log(i) + i · log(2n − i)) .

i=1

Therefore, given Conjecture 1, the algorithm presented in Theorem 1 has
optimal running time.

16

3.7 Connection to Posets

3.7

Connection to Posets

The number f (n,...,n) established in Equation 4 does not only count the number of Young Tableaus of the shape (n, . . . , n) and thus the number of stable
states of the identity, but also has a connection to posets (partially ordered
sets) which we will explain here shortly.

Definition 5. Given a set A and a symmetric, anti-symmetric, and transitive relation  on the elements of A. Then (A, ) is called a partially ordered
set, short: poset.

The specific entities that we want to relate to in poset theory are the linear
extensions of a poset.

Definition 6. Given a poset P = (A, ) with |A| = N . A linear extension
of P is a function f : P → [N ] such that f is bijective and
x  y ⇒ f (x) ≥ f (y),
with ≥ the regular order relation on N.

Our aim is to count the number of linear extensions of a specific poset, the
so-called n × n lattice.

Definition 7. The poset (Xn , ) with Xn = {(i, j) | 1 ≤ i ≤ j ≤ n} and
(i, j)  (k, `) if and only if i ≥ k and j ≥ ` is called the n × n lattice.

The following theorem now relates the number of linear extensions of the n×n
lattice to the number of standard Young Tableaus of the shape (n, . . . , n).

Theorem 7. The number of linear extensions of the n × n lattice is exactly
f (n,...,n) as given in Equation 4.

17

4 General Case

Proof. Given a linear extension f of the n × n lattice, it induces an (n, . . . , n)
Young Tableau by (Aij )i,j=1,...,n = (f (i, j))i,j=1,...,n . Furthermore, the map
f 7→ (f (i, j))i,j=1,...,n is injective.
This relationship gives another possible leverage on Conjecture 1. See Figure
13 for the two possible linear extensions of the 2 × 2 lattice and the two
corresponding Young Tableaus of shape (2, 2).
4 (4, 4)
2 (2, 2)

4 (4, 4)

3 (3, 3)

1 (1, 1)

2

4

1

3

3 (2, 2)

2 (3, 3)

1 (1, 1)

1

3

4

1

2

1

Figure 13: The two possible linear extensions of the 2 × 2 lattice corresponding to the respective (2, 2) Young Tableaus.

4

General Case

In Section 2.1 we made several restrictions. In the following, we will show
that the data structure, as well as the presented results and algorithms do
not suffer from these restrictions.

Not a square number of points. A first assumption was that we are
given exactly N = n2 points in the point set P . How can the structure
handle a general number of points? Given m ∈ N points P = {p1 , . . . , pm }
with n2 ≥ m being the smallest square larger or equal to m. Let xmax be the
largest first coordinate and let ymax be the largest second coordinate, i.e.
xmax := max{p11 , . . . , pm1 },

ymax := max{p12 , . . . , pm2 }.

Add n2 − m auxiliary points of the form (xmax + 1, ymax + 1) to P . In the
algorithm of Theorem 1, these auxiliary points can be forced into the last
two sequences Qn−1 , Qn and thus be placed at the lowest rows or rightmost
columns of the grid where they can be neglected in any neighborhood queries.

18

5 Iterative Parallelized Procedure

Larger dimension than 2. The second assumption was that the points
pi ∈ P are two-dimensional. For higher dimensions, d ≥ 2, consider a ddimensional grid with side length n instead of a matrix, i.e. M ∈ (Rd )n×...×n .
Denote by pi = (pi1 , . . . , pid ), pj = (pj1 , . . . , pjd ) ∈ P two point from P stored
at cells (c1 , . . . , cd ), (c01 , . . . , c0d ) ∈ [n]d in M . There are now d sorting conditions, for each ` ∈ [d] there is a condition:
Either c` 6= c0` or w.l.o.g. c` < c0` and
pi` < pj`
∨(pi` = pj` ∧ pi(`+1) < pj(`+1) )
∨...
∨(pi` = pj` ∧ . . . ∧ pi(d−1) = pj(d−1) ∧ pid < pjd )
∨(pi` = pj` ∧ . . . ∧ pid = pjd ∧ pi1 < pj1 )
∨...
∨(pi` = pj` ∧ . . . ∧ pid = pjd ∧ pi1 = pj1 ∧ . . . ∧ pi(`−2) = pj(`−2)
∧ pi(`−1) < pj(`−1) ).

(5)

That is, in the `th dimension of the grid, two points are compared starting
from the `th coordinate. The comparison is performed cyclically through
all coordinates. pi is smaller than pj if starting from `, the first coordinate
where pi and pj differ is smaller in pi .
Equal points. If there are points pi , pj ∈ P such that pi = pj , no total
ordering can be imposed on the points using Equation (5). This tie can (in
case of equality of the points) be easily broken by declaring pi to be ”smaller”
than pj if and only if i < j.

5

Iterative Parallelized Procedure

A benefit of the neighborhood grid data structure not discussed so far is the
straight forward parallelization of an algorithm creating a stable state. In
this section, we discuss the parallelization of a building algorithm for stable
states, investigate its runtime and how iterative procedures can speed up the
re-building of a stable state in case of addition or deletion of points.

5.1

Parallelization of Stable State Creation

The idea of iterative and parallel creation of stable states is discussed in [3]
at great detail and we are only going to state the basic ideas and results
19

5.1 Parallelization of Stable State Creation

here. However, some questions are not investigated, which we are going to
tackle here. The general scheme for a two-dimensional grid is quite simple
and given in Algorithm 1 (see Figure 14).
Algorithm 1
sorted := false
while ¬sorted do
for each row r do
run a sorting algorithm on r, comparing x
for each row r do
run a sorting algorithm on r, comparing y
if matrix is stable then
sorted := true
Figure 14: Algorithm 1
An immediate question following this algorithm concerns its convergence.
Does it converge and if so, is the final state stable? Malheiros and Walter
did not answer this question in [3], nor did Joselli et al in the original publications [1, 2], where the idea of Algorithm 1 is also used. We will prove the
convergence here.

Theorem 8. Given any point set P = {p1 , . . . , pN | pi ∈ R2 }, placing the
points in a matrix M as described in Section 2.1, and running Algorithm 1
on the matrix, the algorithm converges and yields a stable state of M .

Proof. Given a matrix M as in (1), consider the following expression:
E(M ) =

n
X

i · aij + j · bij ,

(6)

i,j=1

for each sorting step of Algorithm 1, this expression grows, but it can at most
attain N ! many different values.
If the matrix is not in a stable state, i.e. there is a row or column violating the
stable state, sorting this row or column lets expression (6) grow and resolves
the conflict in the given row or column, possibly creating a new conflict in
another row or column. Therefore, a local maximum of this expression is
equivalent to a stable state in the matrix.
20

5.1 Parallelization of Stable State Creation

Figure 15: Step-based odd-even sort on a two-dimensional neighborhood
grid, figure from [3].
Note that the energy functional (6) can easily be extended to higher-dimensional
settings. Given a corresponding version of Algorithm 1 for the higherdimensional case, Theorem 8 holds true for arbitrary dimensional point sets.
In their work [3], Malheiros and Walter investigate a slight variation of Algorithm 1. Namely, they do not perform a full sorting of a row or column, but
rather consider one step of the odd-even sort algorithm. Such step performs
an exchange between all those cells in odd columns and their respective right
neighboring cells, if this pair of cells violates the stable state conditions of
Definition 1. Then, all cells in even columns and their respective right neighboring cells are compared and exchanged if necessary. The same is performed
on all odd rows and even rows, yielding a four step mechanism, see Figure
15.
Note that the argument in the proof of Theorem 8 holds true also for this
algorithm. Therefore, it also converges to a stable state. Question remains
how fast the algorithm works asymptotically. Note that, defying intuition,
elements can cycle using this procedure. An example is given in Figure 16,
where the algorithm depicted in Figure 15 is used.
(3, 1) (2, 2)
(0, 3) (1, 0)

(2, 2) (3, 1)
x

→

(0, 3) (1, 0)

(0, 3) (3, 1)
y

(2, 2) (1, 0)

→

(0, 3) (3, 1)
x

→

(1, 0) (2, 2)

(0, 3) (2, 2)
y

(1, 0) (3, 1)

→

Figure 16: Performing an odd-even sort alternating on all the rows and
columns causes the red element (2, 2) to cycle through the matrix.
Given the possibility of cycling elements, the theoretical asymptotic bounds
of the parallel iterative algorithm remain unclear and only experimental results are available, as presented in [3].

21

5.2 Adaptive Sorting Algorithms for Fast Modifications

Open 2. Given the step-wise odd-even algorithm depicted in Figure 15, what
is its parallelized worst-case runtime aside from the upper bound of O(N !) as
established in the proof of Theorem 8?

First experiments and intuition lead us to state the following conjecture:

Conjecture 2. The step-wise odd-even algorithm depicted in Figure 15 runs
like Bubble-Sort in worst case time of O(N 2 ), after parallelization in O(N ).

5.2

Adaptive Sorting Algorithms for Fast Modifications

The most wide-spread data structure for neighborhood computation, KdTrees, suffer from a severe problem. Namely, if the underlying point set is
slightly altered, the Kd-Tree might become unbalanced. Although there are
some heuristics how to modify Kd-Trees when adding or deleting points, at
some point the Kd-Tree has to be rebuild.

Open 3. Is utilizing an adaptive sorting algorithm on a modified stable state
faster than rebuilding a whole new stable state?

6

Quality of Neighborhood Approximation

As stated above, the neighborhood estimates given by the neighborhood grid
data structure are not necessarily precise. In this section, we will investigate
the quality of the neighborhood approximation.

6.1

Single Point Neighbor

A first question question to answer in this subsection concerns the distance of
two geometrical neighbors from P in the stable state of M . In the following,
we will create a point set P with points p, q ∈ P that are respective nearest
neighbors to each other, but that lie on the exact opposite sites of M .
22

6.2 All Point Nearest Neighbors

Consider the following points p = (0, 0), q = (1, 1), pi = (0, 2 + i/n), i =
1, . . . , n − 1, qi = (1, −2 − i/n), i = 1, . . . , n − 1, and ri,j = (1 − 1/i, 2 + j/n),
i = 2, . . . , n − 1, j = 1, . . . , n. This yields a point set P with n2 points for
n ≥ 2, see Figure 17. Given these points, the following matrix is in a stable
state:
ri,j
p3
p2
p1
q
p

q1
q2
q3
Figure 17: Point set P as given in Section 6.1.

M (P ) =

pn−1 r2,n . . . rn−1,n
..
..
..
.
..
.
.
.
p1
p

q
q1
.. .
.

r2,2 . . . rn−1,2
r2,1 . . . rn−1,n qn−1

Note that the nearest neighbor to p and q in P is q and p respectively.
However, in M (P ), these points lie in the opposing corners of the matrix.
That is, in order to find the geometrically closest neighbor to p in M (P ),
the n-ring around p has to be checked - in other words, all points have to be
checked, which takes O(n2 ) instead of θ(log(n)) as in Kd-Trees.

6.2

All Point Nearest Neighbors

In the previous example we saw that for a single point, its unique nearest
neighbor can be arbitrarily far away in the neighborhood grid. However,
when considering all points, how is the overall estimate? Here, we provide
23

6.2 All Point Nearest Neighbors

an example, where no point has its corresponding neighbor within its one-ring
in the neighborhood grid.
For n ∈ N, 2 | n, consider the following points pi,j = (i, j), qi,j = (i +
n, j + 0.5), ri,j = (i + 0.5, j + n), and si,j = (i + n + 0.5, j + n + 0.5) for
i, j ∈ {0, . . . , n2 − 1}. This yields a point set P with n2 points, see Figure 18.
Given these points, the following matrix is in a stable state:

r0,1

r1,1

r0,0

r1,0

s0,1

s1,1

s0,0

s1,0

q0,1

q1,1

q0,0

q1,0

p0,1 p1,1
p0,0 p1,0
Figure 18: Point set P as given in Section 6.2 for n = 4.

q0, n2 −1 s0, n2 −1 q1, n2 −1 s1, n2 −1
p0, n2 −1 r0, n2 −1 p1, n2 −1 r1, n2 −1
..
..
..
..
.
.
.
.
M (P ) = q0,1
s0,1
q1,1
s1,1
p0,1
r0,1
p1,1
r1,1
q0,0
s0,0
q1,0
s1,0
p0,0
r0,0
p1,0
r1,0

. . . q n2 −1, n2 −1 s n2 −1, n2 −1
. . . p n2 −1, n2 −1 r n2 −1, n2 −1
..
..
.
..
.
.
. . . q n2 −1,1
s n2 −1,1 .
. . . p n2 −1,1
r n2 −1,1
n
. . . q 2 −1,0
s n2 −1,0
. . . p n2 −1,0
r n2 −1,0

Note that the nearest neighbor to pi,j is some pk,` , the nearest neighbor to qi,j
is some qk,` , etc. However, none of the points has its corresponding neighbor
in its one-ring. Expanding this scheme by adding more four-point subsets, it
is easily achievable to create point sets with immediate stable states where
no respective nearest neighbor is in the n4 ring of all points.

24

6.3 Open Questions

6.3

Open Questions

We have given two constructions to create worst case behavior in the neighborhood estimates. However, these constructions do not account for the
average estimate to be expected for a random point cloud. Therefore, we
pose the following question:

Open 4. How good is the average neighborhood estimate of the neighborhood
grid?

So far, this question can only be answered approximately by experiments.
These are going to be performed.
Another open question concerns the procedure for creation of stable states.
From observations, it seems that the sorting produced by the algorithm of
Theorem 1 does not give a result that is as good as performing the following:
As long as a state is not stable, find the two points in the grid such that
exchanging them achieves a maximal grow in expression (6).

Open 5. Does exchanging points by maximal growth of (6) give significantly
better results in the grid than the algorithm of Theorem 1?

Acknowledgments
Martin Skrodzki and Konrad Polthier acknowledge the support by the DFG
SFB/TR 109 ’Discretization in Geometry and Dynamics‘. Martin Skrodzki
also thanks ECMath, BMS, and the German National Academic Foundation
for their support.

25

References

References
[1] Mark Joselli et al. ”A neighborhood grid data structure for massive 3d
crowd simulation on gpu“. In: 2009 VIII Brazilian Symposium on Games
and Digital Entertainment (SBGAMES). IEEE. 2009, pp. 121–131.
[2] Mark Joselli et al. ”Neighborhood grid: A novel data structure for fluids animation with GPU computing“. In: Journal of Parallel and Distributed Computing 75 (2015), pp. 20–28.
[3] Marcelo de Gomensoro Malheiros and Marcelo Walter. ”Simple and efficient approximate nearest neighbor search using spatial sorting“. In:
Graphics, Patterns and Images (SIBGRAPI), 2015 28th SIBGRAPI
Conference. IEEE. 2015, pp. 180–187.
[4] Bruce E. Sagan. The symmetric Group. Springer, 2001.

26

