Geometric Properties of the Monotonic Logical Grid Algorithm for Near Neighbor Calculations

摘要

Because spatial coordinates define a natural ordering of positions, it is always possible to associate with a set of randomly located points in a 3D space, grid indices which are ordered according to their relative positions. Such an indexing scheme can be used to construct a 'Monotonic Logical Grid' (MLG) where adjacent objects in space have close grid indices. Using an MLG to index positions and attributes of objects in computer memory permits a near neighbor algorithm to be based on a 'Maximum index offset,' N sub c, rather than a short range 'cutoff' distance R sub c. An MLG algorithm removes the necessity of having to test distances. Further, 'close' objects will be indexed via contiguous memory. Thus permitting efficient vectorization of computations. Keywords: Statistical analysis; Skew periodic; 3D space; and Nodes. (Author)