The power of parallel projection (Q685515)

In \(d\)-dimensional space, it is shown that from \(d\) parallel projections of a \(k\)-flat into \((k+1)\)-dimensional linear subspaces, each spanned by \(k+1\) of the \(d\) base vectors, one can still reconstruct the \(k\)-flat. Furthermore, it is shown that a \(k\)-flat and a \(j\)-flat intersect in \(d\)- space if and only if they intersect in \({d \choose k+j+1}\) linear subspaces of dimension \((k+j+1)\), in particular, in all \((k+j+1)\)- dimensional subspaces spanned by \(k+j+1\) of the \(d\) base vectors. Thirdly, a similar result holds for the above-below relation of a \(k\)- flat and a \(j\)-flat. Applications of these projection results are \(k\)- dimensional simplex searching in a set of \(n\) points in \(d\)-dimensional space with a structure of size \(O(n^{k+1+\epsilon})\) and \(O(\log n)\) query time, where \(\epsilon>0\) is any fixed real. A second application is ray shooting in axis-parallel boxes in \(d\)-dimensional space, with a structure of size \(O(n^{2+\epsilon})\) and \(O(\log n)\) query time. Both applications make use of multi-layer partition trees.