Geometry and Statistics: Problems at the Interface,

In this paper the author approaches the analysis of statistics algorithms from a geometric viewpoint and uses techniques from computational geometry to develop new, fast algorithms for computing familiar statistical quantities. Such fundamental procedures as sorting and selection play an important role in nonparametric estimation as well as in correlation and regression and the author uses known results to obtain lower bounds on the time required to perform various statistical tests. For some problems, computing the test statistic is NP-hard. While geometric insight is helpful in understanding statistical calculations, the reverse is also true -- statistical methods are employed to analyze the average case of geometric algorithms.