| An Optimal Algorithm for the Hyperplane Depth in R² (1999) | |||||||||||||||
Abstract | |||||||||||||||
| Given an arrangement of n hyperplanes h 1 , . . . , h n # R d the hyperplane depth of a point P # R d is the minimum number of hyperplanes that a ray from P can meet. The hyperplane depth of the arrangement is the maximal depth of points P not in any h i . We give an optimal O(n log n) deterministic algorithm to compute the hyperplane depth of an arrangement in dimension d = 2. Summary Given a set S = {h 1 , . . . , h n } of n hyperplanes in R d , Rousseeuw and Hubert [7] defined the hyperplane depth of a point x # R d to be #(x) = min u:#u#=1 (#(x, u)), (1) where #(x, u) is the number of h i # S that meet the ray {x + tu, t # 0} through x in direction u. A median is a point of maximal depth. When d = 1, S is a set of n given reals and (1) measures the smaller of |{h i # S : h i # x}| and |{h i # S : h i # x}|. A deepest point has depth #n/2# and if we insist that # S, it is the usual median. The depth in (1) describes a multivariate general... | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||