Combinatorial and asymptotic results on the neighborhood grid

In various application fields, such as fluid-, cell-, or crowd-simulations, spatial data structures are very important. They answer nearest neighbor queries which are instrumental in performing necessary computations for, e.g., taking the next time step in the simulation. Correspondingly, various such data structures have been developed, one being the neighborhood grid . In this paper, we consider combinatorial aspects of this data structure. Particularly, we show that an assumption on uniqueness, made in previous works, is not actually satisfied. We extend the notions of the neighborhood grid to arbitrary grid sizes and dimensions and provide two alternative, correct versions of the proof that was broken by the dissatisfied assumption. Furthermore, we explore both the uniqueness of certain states of the data structure as well as when the number of these states is maximized. We provide a partial classification by using the hook-length formula for rectangular Young tableaux. Finally, we conjecture how to extend this to all 2-dimensional cases. • A combinatorial perspective on the Neighborhood Grid spatial data structure • Introducing a polynomial time construction of stable states ( Theorem 3.1 ) • Analyzing the run time of our construction ( Theorem 4.3 and Corollary 4.4 ) • Disproving an implicit uniqueness assumption of previous work ( Proposition 5.5 ) • Sharing several enumerative open problems and conjectures