The Centervertex Theorem for Wedge Depth

Presented at the Canadian Conference on Computational Geometry, 2009, in Vancouver

There are many depth measures on point sets that yield centerpoint theorems.
These theorems guarantee the existence of points of a specified depth, a kind of geometric median.
However, the deep point guaranteed to exist is not guaranteed to be among the input, and often, it is not.
The alpha-wedge depth of a point with respect to a point set is a natural generalization of halfspace depth that replaces halfspaces with wedges (cones or cocones) of angle alpha.
We introduce the notion of a centervertex, a point with depth at least n/(d+1) among the set S.
We prove that for any finite subset S of R^d, a centervertex exists.
We also present a simple algorithm for computing an approximate centervertex.