Journal of Combinatorial Optimization
Volume 16, Number 4, 324-327, DOI: 10.1007/s10878-008-9149-x

A quadratic lower bound for colourful simplicial depth

Tamon Stephen and Hugh Thomas

From the issue entitled "Special Issue on the Franco-Canadian Workshop on Combinatorial Algorithms; Guest Editors: David Bremner, Antoine Deza and Michael Soltys"

View Related Documents

Abstract

We show that any point in the convex hull of each of (d+1) sets of (d+1) points in ℝ d is contained in at least ⌊(d+2)2/4⌋ simplices with one vertex from each set.

Keywords  Computational geometry - Carathéodory theorem - Colourful Carathéodory theorem - Simplicial depth - Colourful simplicial depth

Both authors were supported by NSERC Discovery grants. Additionally, T. Stephen was supported by DFG FG-468 and the Dynamical Systems research focus at the University of Magdeburg.

Fulltext Preview

Image of the first page of the fulltext document