densityreachable

Densityreachable, commonly written as density-reachable, is a concept from density-based clustering, notably DBSCAN. It describes a relationship between two points in a data set with respect to a given neighborhood radius (eps) and a minimum point threshold (minPts). A point q is density-reachable from a point p if there exists a finite sequence p = p0, p1, ..., pk = q such that each successive point pi+1 is directly density-reachable from pi. Direct density-reachability requires that pi be a core point (the number of points in its eps-neighborhood is at least minPts) and that pi+1 lies within distance eps of pi. The last point in the chain (q) can be a core point or a border point; border points are not required to be core themselves, but they must be reachable through a chain of core points.

In DBSCAN, clusters are defined as maximal sets of points that are density-reachable from some core point. Core points are densely surrounded by other points, while border points may be density-reachable from a core point but do not themselves satisfy the core condition. Noise points are those not density-reachable from any core point.

Key properties of densityreachable include its asymmetry (q can be density-reachable from p without the reverse holding) and its transitivity along chains of core points. The concept is closely linked with density-connectedness: two points are density-connected if there exists a core point from which both are density-reachable. Densityreachable is central to the expansion step in DBSCAN and related density-based clustering algorithms.