The Centervertex Theorem for Wedge Depth

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 �-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 �. 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 set S ⊂ R d , a centervertex exists. We also present a simple algorithm for computing an approximate centervertex.