Handbook of Discrete and Computational Geometry, Third Edition
Peter Rousseeuw, Anja Struyf · 2017
As statistical data sets grow larger and larger, the availability of fast and efficient algorithms becomes ever more important in practice. Classical methods are often easy to compute, even in high dimensions, but they are sensitive to outlying data points. Robust statistics develops methods that are less influenced by abnormal observations, often at the cost of higher computational complexity. Many robust methods, especially those based on ranks, are closely related to geometric or combinatorial problems. Recently many other (mostly multivariate) statistical methods have been developed that have a combinatorial or geometric character and are computationally intensive. Techniques of computational geometry appear to be well suited for the development of fast algorithms. Over the last decade, the notion of statistical depth received considerable attention from the computational geometry community. We mainly concentrate on depth and multivariate medians, and in Section 57.3 we list other areas of statistics where computational geometry has recently been of use in constructing efficient algorithms.