Coverage processes on spheres and condition numbers for linear programming

This paper has two agendas. Firstly, we exhibit new results for coverage processes. Let p(n,m,α) be the probability that n spherical caps of angular radius α in Sm do not cover the whole sphere Sm. We give an exact formula for p(n,m,α) in the case α ∈ [π/2,π] and an upper bound for p(n,m,α) in the case α ∈ [0,π/2] which tends to p(n,m,π/2) when α→π/2. In the case α ∈ [0,π/2] this yields upper bounds for the expected number of spherical caps of radius α that are needed to cover Sm. Secondly, we study the condition number C{script}(A) of the linear programming feasibility problem ∃x ∈R{double-struck}m+1Ax ≤ 0, x ≠ 0 where A ∈ R{double-struck}n×(m+1) is randomly chosen according to the standard normal distribution. We exactly determine the distribution of C{script}(A) conditioned to A being feasible and provide an upper bound on the distribution function in the infeasible case. Using these results, we show that E(lnC{script}(A)) ≤ 2 ln(m + 1) + 3.31 for all n > m, the sharpest bound for this expectancy as of today. Both agendas are related through a result which translates between coverage and condition.