I have a collection of closed half-spaces $H\_1, \dots, H\_n \subseteq \mathbb{R}^d$, each given as $H\_i = \{x \in \mathbb{R}^d : a\_i \cdot x \geq c\_i\}$ for some $a\_i \in \mathbb{R}^d$ and $c\_i \in \mathbb{R}$. [This PDF](http://jeffe.cs.illinois.edu/pubs/pdf/Thesis7.pdf) indicates that it's possible to efficiently (in linear time w.r.t. $n$, for fixed $d$) determine whether $H\_1 \cup \cdots \cup H\_n = \mathbb{R}^n$ via linear programming methods. How can one do this? I understand what a linear program is, and I skimmed the cited references, but I don't see how to ask this question as a linear programming problem.


Of course, it's equivalent to ask that $(\mathbb{R}^d \setminus H\_1) \cap \dots \cap (\mathbb{R}^d \setminus H\_n) = \varnothing$. This is *almost* a linear programming problem, but here we are asking if a system of *strict* inequalities has no solution, while [Farkas' Lemma](https://en.wikipedia.org/wiki/Farkas%27_lemma) (for example) only answers this question about systems of non-strict inequalities. Is there perhaps some way to reduce this problem to one about non-strict inequalities?



Algorithm to determine if a union of half-spaces is all of $\mathbb{R}^d$
The intersection of open half-spaces is empty iff the intersection of their closures does not have full dimension, specifically iff it is included in one of the hyperplanes that bound the half-spaces.


That is, in your notation: $\bigcup\_{i=1}^nH\_i=\mathbb R^d$ iff there exists $i=1,\dots,n$ such that the linear program minimizing $a\_i\cdot x$ over $\{x:a\_1\cdot x\le c\_1,\dots,a\_n\cdot x\le c\_n\}$ is either infeasible or has optimal value $c\_i$.


