  We consider several problems that involve lines in three dimensions, and
present improved algorithms for solving them. The problems include (i) ray
shooting amid triangles in $R^3$, (ii) reporting intersections between query
lines (segments, or rays) and input triangles, as well as approximately
counting the number of such intersections, (iii) computing the intersection of
two nonconvex polyhedra, (iv) detecting, counting, or reporting intersections
in a set of lines in $R^3$, and (v) output-sensitive construction of an
arrangement of triangles in three dimensions.
  Our approach is based on the polynomial partitioning technique.
  For example, our ray-shooting algorithm processes a set of $n$ triangles in
$R^3$ into a data structure for answering ray shooting queries amid the given
triangles, which uses $O(n^{3/2+\varepsilon})$ storage and preprocessing, and
answers a query in $O(n^{1/2+\varepsilon})$ time, for any $\varepsilon>0$. This
is a significant improvement over known results, obtained more than 25 years
ago, in which, with this amount of storage, the query time bound is roughly
$n^{5/8}$. The algorithms for the other problems have similar performance
bounds, with similar improvements over previous results.
  We also derive a nontrivial improved tradeoff between storage and query time.
Using it, we obtain algorithms that answer $m$ queries on $n$ objects in \[
\max \left\{ O(m^{2/3}n^{5/6+\varepsilon} + n^{1+\varepsilon}),\;
O(m^{5/6+\varepsilon}n^{2/3} + m^{1+\varepsilon}) \right\} \] time, for any
$\varepsilon>0$, again an improvement over the earlier bounds.
