Uniform grids are useful in many of the following applications. This idea is intended to be just sophisticated enough to solve the problem, without being so complicated that it is difficult to implement, including the messy special cases, and parallelize. (1977)
The concept, which is useful for culling pairs of objects that may intersect, is to overlay a uniform grid on the data. Then iterate over the elements, finding which grid cells each passes thru. Finally, iterate over the cells, comparing pairs of elements that pass thru the same cell. Implementing this properly requires some attention to detail. This method works well even when the data is unevenly distributed, where one's first impulse would be to use the, more complicated, quadtree.
One application is a parallelizable algorithm finds all the intersections among a large number of small line segments in E2. The time to find all K intersections among N line segments is an expected θ(N+K), altho an adversary can choose input to raise that to N2 . However no real data sets have exhibited that behavior. Data has been used from cartography, VLSI design, and nonuniform meshes. This is a common operation in many higher-level operations such as boolean combinations. Papers include: