Exact computation of angular halfspace depth

Abstract The angular halfspace depth ( $$ahD$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>ahD</mml:mi> </mml:mrow> </mml:math> ) 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$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>ahD</mml:mi> </mml:mrow> </mml:math> in any dimension d . We proceed in two steps: (i) We express $$ahD$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>ahD</mml:mi> </mml:mrow> </mml:math> as a generalized (Euclidean) halfspace depth in dimension $$d-1$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>d</mml:mi> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:math> , using a projection approach. That allows us to develop fast exact computational algorithms for $$ahD$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>ahD</mml:mi> </mml:mrow> </mml:math> in dimensions $$d=1, 2, 3$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>d</mml:mi> <mml:mo>=</mml:mo> <mml:mn>1</mml:mn> <mml:mo>,</mml:mo> <mml:mn>2</mml:mn> <mml:mo>,</mml:mo> <mml:mn>3</mml:mn> </mml:mrow> </mml:math> . (ii) In spaces of dimension 3]]d 3 we design an inductive procedure that reduces the dimensionality d in the computation of $$ahD$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>ahD</mml:mi> </mml:mrow> </mml:math> , until the algorithms for $$d \le 3$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>d</mml:mi> <mml:mo>≤</mml:mo> <mml:mn>3</mml:mn> </mml:mrow> </mml:math> can be used. Using our advances we develop a family of powerful algorithms for the computation of $$ahD$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>ahD</mml:mi> </mml:mrow> </mml:math> 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$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>ahD</mml:mi> </mml:mrow> </mml:math> of multiple points with respect to the same dataset is substantially faster than the same task for the classical (Euclidean) halfspace depth.