Computational Geometry and Statistical Depth Measures

The computational geometry community has long recognized that there are many important and challenging problems that lie at the interface of geometry and statistics (e.g., Shamos, 1976; Bentley and Shamos, 1977). The relatively new notion of data depth for non-parametric multivariate data analysis is inherently geometric in nature, and therefore provides a fertile ground for expanded collaboration between the two communities. New developments and increased emphasis in the area of multivariate analysis heighten the need for new and efficient computational tools and for an enhanced partnership between statisticians and computational geometers.Over a decade ago point-line duality and combinatorial and computational results on arrangements of lines contributed to the development of an efficient algorithm for two-dimensional computation of the LMS regression line (Souvaine and Steele, 1987; Edelsbrunner and Souvaine, 1990). The same principles and refinements of them are being used today for more efficient computation of data depth measures. These principles will be reviewed and their application to statistical problems such as the LMS regression line and the computation of the half-space depth contours will be presented. In addition, results of collaborations between computational geometers and statisticians on data-depth measures (such as half-space depth and simplicial depth) will be surveyed.