| The field of Computational Geometry deals with the systematic study of algorithms and data structures for geometric objects [461. 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. [128, 19]).; Data depthis a statistical analysis method that assigns a numeric value to a point, corresponding to its centrality relative to a data set. It is inherently geometric in nature, providing ample opportunity for computational geometry based research. Some examples of data depth functions are half-space depth, simplicial depth, convex-hull peeling depth, L1 depth and regression depth. Data depth has significant potential as a data analysis tool. However, the lack of efficient computational tools for depth based analysis of large high-dimensional data sets is one of the main reasons it is not yet in widespread use.; The goal of this work is to enhance knowledge on the data depth concept, using computational geometry tools and techniques. In particular: (1) We identify two approaches for defining estimators based on the concept of data depth and use them to analyze depth contours, enclosing regions of increasing depth (Chapter 2). (2) We present new algorithms for problems of dynamically computing half-space depth contours (Chapter 3) and of computing the simplicial depth median, based on a novel approach for topologically sweeping the complete graph (Chapter 4) which is of independent interest. (3) We propose a framework to evaluate any depth function and apply it to the analysis of two rectilinear depth functions, box depth and dominance depth (Chapter 5). |
