THE POWER OF PARALLEL PROJECTION

It is shown that from d projections of a k-flat into (k + 1)-dimension al linear subspaces one can still reconstruct the k-flat. Furthermore, we show that a k-flat and a j-flat intersect in d-space if and only i f they intersect in (d/k+j+1) linear subspaces of dimension (k + j + 1 ) (and which are independent, of the k-flat and the j-flat). An applic ation of these projection results is k-dimensional simplex searching f or a set S of n points in d-dimensional space with a structure of size O(n(k+1+epsilon)) and O(log n) query time, for arbitrarily small posi tive epsilon. A second application is ray shooting in axis-parallel bo xes in d-dimensional space, with a structure of size O(n2+epsilon) and O(log n) query time.