Loading…

Combinatorial and Asymptotical 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 su...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2023-10
Main Authors: Skrodzki, Martin, Reitebuch, Ulrich, McDonough, Alex
Format: Article
Language:English
Subjects:
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 \emph{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.
ISSN:2331-8422