Spatial data and geometry

Find the nearest neighbor of every atom in a snapshot of 100,000 atoms the direct way and you compute 5 × 10⁹ pair distances; the full distance matrix would take 80 GB. A KD-tree sorts the points once into nested boxes and then searches only the boxes near each atom, so the work grows like n log n instead of n². Do not build a full distance matrix for more than a few thousand points.

Questions about points in space come from everywhere: the pair correlation function of a simulated liquid, the territories of cells in a tissue section, earthquake epicenters clustering along a fault, a laser scan of a building, the survey points of an outcrop. Many reduce to two structures. The Delaunay triangulation joins each point to its natural neighbors, and the Voronoi diagram gives each point the region closer to it than to any other; they are two views of the same thing. For 10,000 random points in a square, an interior point has 5.99 neighbors on average, and Euler's formula for planar graphs says the mean tends to exactly six.

In Python, scipy.spatial has KDTree, with query for the k nearest neighbors and query_ball_point for all points within a radius, and Delaunay, Voronoi, and ConvexHull, which wrap the Qhull library. scipy.spatial.distance.cdist computes distance matrices that fit in memory, and KDTree takes a boxsize for the periodic boundaries of a simulation box. In Julia, NearestNeighbors.jl provides KDTree, knn, and inrange, and Distances.jl computes distance matrices with pairwise.

Start with nearest-neighbor queries on a KD-tree, which most of the rest builds on, then the Delaunay triangulation and the Voronoi diagram, then the pair correlation function. Points on the globe belong to maps and geospatial data, and connections that are not distances to networks and graphs.

What belongs here

Points in space and the questions about them: nearest-neighbor search with KD-trees, distance matrices, Delaunay triangulation and Voronoi diagrams, convex hulls, point-cloud processing, and spatial statistics such as the pair correlation function. Points on the Earth's surface and map projections belong to geospatial.