Nearest Neighbors - ProkopHapala/SimpleSimulationEngine GitHub Wiki

Nearest neighbor search has complexity N^2. We can reduce it to NlogN or almost linear N by use of special datastructures, such as HashMap or BufferGrid. In 2D and 3D HashMap can be used directly (for each query point $i$ we simply explore all neighboring grid cells). However in more dimensional spaces this is not possible since there is too many such neighboring cells ( 3^D resp. 2^D depending on whether we insert point into just one box, or into all boxes witch which it bounding sphere overlaps ).

In more dimensional space we have to use several independent HashMaps or grids from which we quarry independently. Each of these hashmaps returns it own set of possible neighbors. Only common intersection from all these sets is than considered as possible neighbor. For this narrow subset true pair-wise distance is computed.

Algorithm for HashMap neihbor quarry of atomic structures

• For structure i evaluate real valued hashes (h_1,h_2,...h_N) (e.g. projection on planewaves for each atom type), and discretize it to integer hashes (ih_1,ih_2,...ih_N)
• For HashMap_k (1D,2D or 3D) quarry compound index ind_k = pack( hi_i(k), hi_(i(k)+1), hi_(i(k)+2) ) to obtain set S_k
  • if first set total set

cellNeighs2D = [(0,0), (-1,0),(+1,0), (0,-1),(0,+1), (-1,-1),(-1,-1), (-1,+1),(+1,-1) ]

def getPossibleNeighbors( geometry, hashMaps, hashFuncs ):
    result = None
    for hashMap,hashFunc in zip( hashMaps, hashFuncs ):
        hashvec    = [ hf(geometry) for hf in hashFunc ] # compute real valued hashes (properly scaled by step )
        icell      = [ int(h) for h in hashvec ] # 1D,2D or 3D index of grid cell
        aspect_set = {}
        for dicell in cellNeighs2D:
            found_list = hashMap.getInBins( icell + dicell)
            aspect_set.insert( found_list )
        if( result is None ):
             result_set = aspect_set   # initialize result
        else:
             result_set = { x if ( x in result_set ) for x in aspect_set }    # make intersection with previous result
    return result