Suppose you're writing a video game that takes place on a large rectangle (2d).  You have a large list of entities (monsters, spells, and so forth, represented as points) living on this rectangle, and you need to know which pairs are within Euclidean distance 1 of each other, and for each such pair, what their distance is, so you can figure out how each affects its neighbors.  This information must be updated every frame of the game.In this particular case, the entities are moving rapidly, but we can assume that they often retain their relative positions.  For example, groups of them may move in formation, or entities may move like cars on a highway.  We can also assume that their minimum distance has some bound, or at very least, there is an upper bound on the number of neighbors each node can have.Brute force is O(n^2) per frame.  Using a data structure such as a KD-tree or a Delaunay triangulation, we may be able to improve that to O(n log n).  But since the relative structure of the group is roughly constant, is there a way to achieve typical-case linear time?If I were to get serious about this problem myself, I'd start with a Delaunay triangulation, see if I could use it to efficiently find the pairs of points of less than unit distance, and then see if there was an efficient way to use the previous frame's Delaunay triangulation to accelerate generating the current frame's triangulation.This is mostly academic for me, since my tests in Python so far reveal that brute force has the best wall clock time.  But surely I can't be the only person curious about this problem -- anyone who has ever written a game must have given it some thought.  SciPy's KDTrees can produce the data I'm looking for with sparse_distance_matrix but the wall clock time for building and querying a KD tree was much worse than brute force in the cases I tried.  Perhaps KDTrees involve more Python and less C than the brute force code I used (scipy.spatial.distance.pdist), or perhaps the time coefficient for the KDTrees is just very high on its own.
Bounded pairwise distance on moving points
algorithms;data structures;computational geometry;computer games