The α-Embracing Countour

Every notion of depth induces a stratification of the plane in regions of points with the same depth with respect to a given set of points. The boundaries of these regions, also known as depth-contours, are an appropriate tool for data visualization and have already been studied for some depths like Tukey depth [5, 7, 8, 9] and Delaunay depth [3, 6]. The contours also have applications in quality illumination as is the case of good α-illumination [2]. The first α-depth contour is also known as the α-embracing contour. We prove that the first α-depth contour has linear size and we give an algorithm to compute it in O(n2) running time and O(n) space. 1 Introduction and Related Work Data depth has been considered as a measure to check how deep or central a given point is with respect to a multivariate distribution. A notion of depth induces a stratification of the plane in regions of points that share their depth with respect to a given set of points. The boundaries of these regions are called depth-contours and they are used as a tool for data visualization since they provide a quic