densityreachability

Density reachability is a concept used in density-based clustering to describe when one point in a data set can be reached from another by traversing a chain of neighboring points that meet a density criterion. It underpins how clusters are formed in algorithms such as DBSCAN and OPTICS, which rely on dense regions rather than purely geometric proximity.

Formally, with parameters ε (radius) and MinPts (minimum points), a point p is a core point if the ε-neighborhood of p contains at least MinPts points. A point q is density-reachable from p with respect to ε and MinPts if there exists a chain p = p0, p1, ..., pk = q such that each pi+1 lies in the ε-neighborhood of pi, and every pi for i < k is a core point. The final point q need not be a core point. In this sense, density reachability is generally directional: p can density-reach q without q necessarily density-reaching p.

Related concepts include density connectivity: two points p and q are density-connected if there exists a point o such that both p and q are density-reachable from o. Density reachability is transitive along a chain of core points and is used to define clusters as sets of points density-reachable from core points within the same cluster.

In practice, DBSCAN forms clusters by aggregating all points that are density-reachable from some core point, while OPTICS and related methods use reachability relationships to build an ordering or a reachability plot that reveals the cluster structure without committing to a fixed ε.