The Centervertex Theorem for Wedge Depth
Gary L. Miller, Todd Phillips and Donald R. Sheehy
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}}