Point set stratification and Delaunay depth

In the study of depth functions it is important to decide whether a depth function is required to be sensitive to multimodality. An analysis of the Delaunay depth function shows that it is sensitive to multimodality. This notion of depth can be compared to other depth functions such as the convex and location depths. The stratification that Delaunay depth induces in the point set (layers) and in the whole plane (levels) is investigated. An algorithm for computing the Delaunay depth contours   associated with a point set in the plane is developed. The worst case and expected complexities of the algorithm are O(nlog2n) and O(nlogn)O(nlogn), respectively. The depth of a query point p with respect to a data set S in the plane is the depth of p   in S∪{p}S∪{p}. The Delaunay depth can be computed in O(nlogn)O(nlogn) time, which is proved to be optimal, when S and p are given in the input.