We present an algorithm for locating a query point $q$ in an arrangement of $n$ hyperplanes in $d$-space. The size of the data structure is $O(n sup d$) and the time to answer any query is $O($log $n)$. Unlike previous data structures, our solution will also report, in addition to the face of the arrangement that contains $q$, the first hyperplane that is hit (if any) by shooting the point $q$ in some fixed direction. Actually, if this ray-shooting capability is all that is needed, or if one only desires to know a single vertex of the face enclosing $q$, then the storage can be reduced to $O(n sup d^/($log $n) sup {left ceiling ^d/2^ right ceiling - epsilon}^)$, for any fixed $epsilon ^ > ^ 0$.

This technical report has been published as

Point Location Among Hyperplanes and Unidirectional Ray-Shooting. Bernard Chazelle and Joel Friedman, Computational Geometry: Theory and Applicaitons 4(2), 1994, pp. 53-62.