Natural neighbor sorting on the n-dimensional sphere

摘要

The natural neighbor order of an n-dimensional data set in Euclidean space is obtained by identifying all n-dimensional hyperspheres through n + 1 or more of the data and such that no datum lies within any hypersphere. Two data are natural neighbors if, and only if, they share such a hypersphere. In this note, the concept of natural neighbor order is extended to n-component directional data, as normalized onto an n-dimensional sphere, and an algorithm for computing the natural neighbor order on that sphere is given. This provides an efficient method for finding modes and for estimating radial density contours of directional data.