Colourful linear programming

We consider the following Colourful generalization of Linear Programming: given sets of points S₁, ..., S _k ⊕ℝd, referred to as colours, and a point b ε ℝd, decide whether there is a colourful T = {s₁,..., s _k } such that b ε conv(T), and if there is, find one. Linear Programming is obtained by taking k = d + 1 and S₁ = ... = S _d +1. If k = d + 1 and b ε ∩_i=1d+1 conv(S_i) then a solution always exists, but finding it is still hard. We describe an iterative approximation algorithm for this problem, that finds a colourful T whose convex hull contains a point ε-close to b, and analyze its Real Arithmetic and Turing complexities. We then consider a class of linear algebraic relatives of this problem, and give a computational complexity classification for the related decision and counting problems that arise. In particular, Colourful Linear Programming is strongly NP-complete. We also introduce and discuss the complexity of a hierarchy of (w₁, w₂)-Matroid-Basis-Nonbasis problems, and give an application of Colourful Linear Programming to the algorithmic problem of Tverberg's theorem in combinatorial geometry.