  We develop data structures for intersection queries in four dimensions that
involve segments, triangles and tetrahedra. Specifically, we study three main
problems: (i) Preprocess a set of $n$ tetrahedra in $\reals^4$ into a data
structure for answering segment-intersection queries amid the given tetrahedra
(referred to as \emph{segment-tetrahedron intersection queries}). (ii)
Preprocess a set of $n$ triangles in $\reals^4$ into a data structure that
supports triangle-intersection queries amid the input triangles (referred to as
\emph{triangle-triangle intersection queries}). (iii) Preprocess a set of $n$
segments in $\reals^4$ into a data structure that supports
tetrahedron-intersection queries amid the input segments (referred to as
\emph{tetrahedron-segment intersection queries}). In each problem we want
either to detect an intersection, or to count or report all intersections. As
far as we can tell, these problems have not been previously studied.
  For problem (i), we first present a "standard" solution which, for any
prespecified value $n \le s \le n^6$ of a so-called storage parameter $s$,
yields a data structure with $O^*(s)$ storage and expected preprocessing, which
answers an intersection query in $O^*(n/s^{1/6})$ time (here and in what
follows, the $O^*(\cdot)$ notation hides subpolynomial factors). For problems
(ii) and (iii), using similar arguments, we present a solution that has the
same asymptotic performance bounds. We then improve the solution for problem
(i), and present a more intricate data structure that uses $O^*(n^{2})$ storage
and expected preprocessing, and answers a segment-tetrahedron intersection
query in $O^*(n^{1/2})$ time.
