python - Efficient nearest neighbour search when list is growing? -

i've been rewriting old maze type thing did fun, though instead of being maze it's bit more abstract , shrinks down, can't if location in locations search.

i've done basic nearest neighbour search , have tried optimise little, it's still slow, in every 10x more nodes, 1000x more calculations needed (167 billion @ 10,000 nodes, collision checking), don't think there's more can done this.

here's code edited work itself, nodes class , iterate through each 1 , grab size/location attribute (changed node[0] , node[1]). imagine node_list has thousands of values.

dimensions = 3 dimensions_range = range(dimensions) def collision_check(node_list, location, size, bounds=none):      #check new node within bounds (if set)     if bounds:         in dimensions_range:             if not bounds[0][i] + size <= location[i] <= bounds[1][i] - size:                 return true      #find if nodes overlapping     node in node_list:         size_total = size + node[0]         distance = [abs(a - b) a, b in zip(location, node[1])]          #take these 2 lines out , time taken doubles         if max(distance) > size_total:             continue          #square 1 half of pythagoras         distance_total = sum(pow(i, 2) in distance)         if distance_total < pow(size_total, 2):             return true      return false  node_list = [ [0.5, (0, 0, 0)], [0.5, (0, 0, 1)] ]  new_size, new_loc = [0.5, (0, 0, 2)] print collision_check(node_list, new_loc, new_size) #no collision  new_size, new_loc = [0.6, (0, 0, 2)] print collision_check(node_list, new_loc, new_size) #collision 

i thinking of segment type idea, nodes have dimensions, 1 point potentially cross 4 segments, meaning i'd have if any(i in existing_segments in current_segments) check on every node, sounds lot possibly end slower. i've heard of kd trees , don't understand them, i'm guessing wouldn't cope points being added as looked up.

this isn't important anyway, i'm curious if there's better way isn't ridiculously advanced.