Computational Geometry

Department of Computer Science

Half Space Depth Contours

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.

Figure

The half-space depth contours. The red points are the original data points

Related Papers

[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

Code

A README file describing how to use the code.

A tar.zip version of the code.

Related Pages