Pat suggests the following idea for the upperbound of halfspace depth

For data set in dimension d, randomly select d points, find a normal vector v of the hyperplane defined by the d points, and project all points in the data set onto v. For a point p, the number of points on one side of p is an upperbound of the halfspace depth of p.