Statistics and Computing Вычислительная теория и математика

Exact computation of angular halfspace depth

Rainer Dyckerhoff, Stanislav Nagy
Springer Nature · 2025-08-18 · DOI 10.1007/s11222-025-10700-z

Аннотация

Abstract The angular halfspace depth ( $$ahD$$ ahD ) was, already in 1987, the first depth function proposed for the nonparametric analysis of directional data. Mainly due to its presumed high computational cost and lack of efficient computational algorithms, it was never widely used in directional data analysis. We address the problem of the exact computation of $$ahD$$ ahD in any dimension d . We proceed in two steps: (i) We express $$ahD$$ ahD as a generalized (Euclidean) halfspace depth in dimension $$d-1$$ d - 1 , using a projection approach. That allows us to develop fast exact computational algorithms for $$ahD$$ ahD in dimensions $$d=1, 2, 3$$ d = 1 , 2 , 3 . (ii) In spaces of dimension 3]]d 3 we design an inductive procedure that reduces the dimensionality d in the computation of $$ahD$$ ahD , until the algorithms for $$d \le 3$$ d ≤ 3 can be used. Using our advances we develop a family of powerful algorithms for the computation of $$ahD$$ ahD in any dimension d . Our procedures are implemented efficiently in with an interface in . A detailed analysis of the complexity of the novel algorithms is performed. Surprisingly, we show that computing $$ahD$$ ahD of multiple points with respect to the same dataset is substantially faster than the same task for the classical (Euclidean) halfspace depth.

Читать у издателя →