The Half space Depth (also known as Location depth) of a given point a relative to a data set P is the minimum number of points of P lying in any closed halfplane determined by a line through a.
We present an implementation for computing half-space depth Contours based on an algorithm presented in [1]. The algorithm uses topological sweep of the dual arrangement of lines to compute the depth contours.
It was implemented based on the Topological sweep code.
The half-space depth contours. The red points are the original data points
[1] "Fast implementation of depth contours using topological sweep,'' K. Miller, S. Ramaswami, P. Rousseeuw, T. Sellares, D. Souvaine, I.
Streinu, A. Struyf. Proceedings of the Twelfth ACM-SIAM Symposium on Discrete Algorithms, Washington, DC, January, 2001. Postscript version[2]" Efficient Computation of Location Depth Contours by Methods of Combinatorial Geometry", K. Miller, S. Ramaswami, P. Rousseeuw, T. Sellares, D. Souvaine, I. Streinu, A. Struyf. Statistics and Computing, 2003, Postscript version.
[3]"Topological Sweep in Degenerate cases", E. Rafalin, D. Souvaine, I. Streinu, ALENEX 02, January 2002, San-Francisco, CA, Postscript version, Pdf version
[4] "Topologically Sweeping an arrangement", H.Edelsbrunner, L. Guibas, J. of Computer and System Sciences 38, 165-194, 1989
A README file describing how to use the code.
A tar.zip version of the code.