__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

** 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.