(abbreviated abstract) Questions about lines in space arise frequently as subproblems in 3-dimensional Computational Geometry. In this paper we study a number of fundamental combinatorial and algorithmic problems involving arrangements of n lines in 3-dimensional space.