Point Location and Depth Contours

Let X be a set of points and P an arbitrary point, not necessarily in X. The location depth in 2-dimensions is defined to be smallest number of points in X to lying on either side of a halfplane defined by any line going through P. This definition can be extended to any dimension, but the focus of this project will be the 2-dimensional case.

The main motivation for the study of this problem comes from the field of statistics. The Tukey median can be described as the center of gravity of the deepest conntour. It can serve as median measure for data that has more than 1-dimension.

The main task in this problem is to contruct depth countours. Depth contours are defined as for a fixed integer k, the set of points in the plane with location depth greater than or equal to k is a convex polygonal region, called the k-th depth contour. From this definition we can see that a Convex Hull is actually the 1-depth contour.

There are many algorithms for computing the Convex Hull of a set of points. The technique that is of interest to us is the method using duality. Taking the set of points that are given, map those points to the dual plane, we now are left with a set of lines. We can now obtain the upper and lower hull of our points by taking note of the lines in the dual that are on the upper and lower envelope, as seen in the image below. The intersections of the upper envelope will correspond to the lines that define the upper hull, and likwise the lower envelope.

The upper and lower envelope for a set of n lines can also be defined as the 1-level and n-level of the arrangement. As with k-depth contours in the primal, the dual we will be concerned with the k-level of the arrangement. This is the set of points that have at most k-1 lines strickly above it, and at most n-k lines strickly below it. The intersections along the k-level will define lines in the primal called a k-divider, which is a line that has exactly k-1 points of a point set X on one side and at most n-k points on the the other side.

The Algorithm

There are three steps to the algorithm that we are going to discuss. The steps will use some of the basic theory we have previously discussed. Let's take a look at the pseudo-code first.

Step 1: This step is quite simple, all that is done is the points given to us for our problem are mapped to the dual plane. As we have seen above there are key relationships between the primal and the dual with regard to finding depth contours. Remember each intersection of two or more lines defines a k-divider and may be part of the k-th depth contour, but first we have to find those intersections.

Step 2: This step uses a topological sweep of our line arrangements to determine the location and the depth of the intersections in the dual. We will record the level of each intersection so that this information can be used in the third and final step.

Step 3: We will now take the intersections points of the dual and map them to the primal. Each line has been assigned a level in the previous step of the algorithm. Then each depth contour will be computed by taking the intersection of the halfplanes defined by the lines of that respective level.

This method for finding depth contours was first suggested in 1987 by Cole, Sharir and Yap. In 2000 though the algorithm was modified by Miller et al. to incorporate a topological sweep.

Let's look at the animated example below which demonstrate the computation of finding the first two contour depths.