Technical Reports

Data depth is a statistical analysis method that assigns a numeric value to each point, corresponding to its centrality relative to a data set. Depth contours, nested contours that enclose regions with increasing depth, provide a powerful method to visualize, quantify and compare data sets. We present the first dynamic algorithm for computing the half-space depth contours of a set of n points in R^2 in O(n log n) and O(n log^2 n) time per operation for two flavors of depth contours and in quadratic space, an improvement over the static version of O(n^2) time per operation. Our analysis characterizes key constraints on potential contour changes under insertion and deletion, that have not been identified before.