An implementation to find the Tukey Median of a planar point set in O(nlog^5 n) expected time

Abstract

The Tukey Median of a planar point set is a the point of greatest depth among all other points. Depth is defined by creating halfspaces and observing how many points lie to the right or the left of that halfspace. For example, a depth of 1 means that a halfspace can be drawn such that at least one point from the original point set is to one side and the all the other points are on the other side. The Tukey Median is found by finding the contour, which is a convex object, of greatest depth and then taking the center of mass of that object. The original algorithm designed by Jiri Matousek relied on rather complex algorithmic tools that remain theoretical. However, through randomization, these tools can be replaced and simplified tremendously. My talk will be a brief journey into this problem and will discuss several concepts that are important to computational geometry.