The Centervertex Theorem for Wedge Depth

CCCG: The Canadian Conference in Computational Geometry
2009

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.

@inproceedings{miller09centervertex, Title = {The Centervertex Theorem for Wedge Depth}, Author = {Gary L. Miller and Todd Phillips and Donald R. Sheehy}, Booktitle = {CCCG: Canadian Conference in Computational Geometry}, Year = {2009}}