Technical Reports

Display by Author: A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z
Search by for:
Dynamic Update of Half-space Depth Contours
Authors: Burr, Michael A.; Rafalin, Eynat; Souvaine, Diane L.
Date:Feburary 2006
Download Formats: [PDF]
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.

Faculty: for help posting a technical report please visit the User Guide.