  Set cover, over a universe of size $n$, may be modelled as a data-streaming
problem, where the $m$ sets that comprise the instance are to be read one by
one. A semi-streaming algorithm is allowed only $O(n\, \mathrm{poly}\{\log n,
\log m\})$ space to process this stream. For each $p \ge 1$, we give a very
simple deterministic algorithm that makes $p$ passes over the input stream and
returns an appropriately certified $(p+1)n^{1/(p+1)}$-approximation to the
optimum set cover. More importantly, we proceed to show that this approximation
factor is essentially tight, by showing that a factor better than
$0.99\,n^{1/(p+1)}/(p+1)^2$ is unachievable for a $p$-pass semi-streaming
algorithm, even allowing randomisation. In particular, this implies that
achieving a $\Theta(\log n)$-approximation requires $\Omega(\log n/\log\log n)$
passes, which is tight up to the $\log\log n$ factor. These results extend to a
relaxation of the set cover problem where we are allowed to leave an
$\varepsilon$ fraction of the universe uncovered: the tight bounds on the best
approximation factor achievable in $p$ passes turn out to be
$\Theta_p(\min\{n^{1/(p+1)}, \varepsilon^{-1/p}\})$. Our lower bounds are based
on a construction of a family of high-rank incidence geometries, which may be
thought of as vast generalisations of affine planes. This construction, based
on algebraic techniques, appears flexible enough to find other applications and
is therefore interesting in its own right.
