wellseparated

Well-separated is a mathematical term used to describe collections of points or subsets whose pairwise distances are bounded below by a positive constant. In a metric space (X, d), a subset P is δ-separated if there exists δ > 0 such that d(p, q) ≥ δ for every pair of distinct points p, q in P. If a collection is δ-separated for some δ, it is often described as well-separated (the separation constant δ may depend on the collection).

In Euclidean space, a finite δ-separated set has a limited density: the balls of radius δ/2 around the points are disjoint, so the number of points inside a region is controlled by its volume. The concept generalizes to other metric spaces and appears in areas such as packing problems, sampling theory, and harmonic analysis. Related notions include ε-separated and uniformly discrete sets. Delone (or Delone) sets are those that are both δ-separated and relatively dense, balancing separation with coverage of space.

A notable specialized use is the well-separated pair decomposition (WSPD) in computational geometry. Given a finite point set P in R^d and a separation parameter t > 0, a pair of nonempty, disjoint subsets (A, B) of P is t-well-separated if the minimum distance between A and B is at least t times the larger of diam(A) and diam(B). WSPD enables fast approximation algorithms for N-body problems and various geometric queries, by treating points in well-separated clusters as distant pairs.

Examples include the integer lattice Z^n with unit spacing, which is 1-separated, and scaled versions thereof. The term is used across disciplines, wherever a quantitatively controlled separation of points or clusters is advantageous.