PhD Defense: Computational Problems on Depth Measures Combining Combinatorics and Geometry

A fundamental concept in statistics is the measure of the "centrality" of a point relative to a multidimensional point set. This generalizes the one-dimensional concept of the median and has been modeled in statistics through depth functions. Such a function assigns each point in space a numeric value that increases with the point's degree of centrality. This topic has been extensively studied in statistics, and numerous depth functions have been proposed and analyzed.
Broadly speaking, depth functions can be classified into two groups: those that are based on geometric properties, such as distances, and those that are based on combinatorial properties, such as counts. In this dissertation, we introduce two new depth functions that combine both of these elements. We explore these functions from both a mathematical and computational perspective.
The first depth function is called the Shapley-value depth. This is based on a classical concept from game theory, called the Shapley value, which measures the contribution of each player, when working in a cooperative setting. In our case, the points serve as players, and contributions are measured geometrically in terms of volume, area, or mean width.
The second depth function is called the projective halfspace metric depth. This adapts the well-known Tukey depth by including a component based on distances (rather than counts) of points to a hyperplane. This depth function can be interpreted as the minimum total distance that points in a point set need to be moved so that the query point is exposed to the exterior of the convex hull.
We show that both functions possess nice mathematical properties, and we present efficient algorithms and data structures to compute or approximate them. We also study a recently proposed depth function, called the hyperplane distance depth. We develop a space-efficient data structure that can answer approximation queries to this function.