|
Friday, November 23, 2012 |
|
|
|
|
Combinatorial, computational, and geometric approaches to the colourful simplicial depth |
|
|
In statistics, there are several measures of the depth of a point $p$ relative to
a fixed set $S$ of sample points in dimension $d$. One of the most intuitive is
the simplicial depth of $p$ introduced by Liu (1990), which is the number of
simplices generated by points in $S$ that contain $p$. Obtaining a lower bound for
the simplicial depth is a challenging problem. Carathéodory Theorem can be
restated as: The simplicial depth is at least 1 if $p$ belongs to the convex hull
of $S$. Bárány (1982) showed that the simplicial depth is a least a fraction
of all possible simplices generated from $S$. Gromov (2010) improved the fraction
via a topological approach. Bárány's result uses a colourful version of
Carathéodory Theorem leading to the associated colourful simplicial depth. We
present recent generalizations of the Colourful Carathéodory Theorem due to
Arocha et al. and Holmsen et al. and our strengthening of these. We provide a new
lower bound for the colourful simplicial depth improving the earlier bounds of
Bárány and Matou{\v s}ek and of Stephen and Thomas. Computational approaches
for small dimensions and the colourful linear programming feasibility problem
introduced by Bárány and Onn are discussed. |