2014/02/14 by Pauline Sarrabezolles, Sarrabezolles, Pauline
Computer Science · #Topological and Geometric Data Analysis #Computational Geometry and Mesh Generation #Advanced Graph Theory Research
paper · pdf · doi:10.48550/arxiv.1402.3413
Given d+1 sets of points, or colours, S1,…,Sd+1 in \mathbb Rd, a colourful simplex is a set T⊆\bigcupi=1d+1Si such that |T∩ Si|≤ 1, for all i∈\1,…,d+1\. The colourful Carathéodory theorem states that, if \mathbf 0 is in the convex hull of each Si, then there exists a colourful simplex T containing \mathbf 0 in its convex hull. Deza, Huang, Stephen, and Terlaky (Colourful simplicial depth, Discrete Comput. Geom., 35, 597--604 (2006)) conjectured that, when |Si|=d+1 for all i∈\1,…,d+1\, there are always at least d2+1 colourful simplices containing \mathbf 0 in their convex hulls. We prove this conjecture via a combinatorial approach.