Published on *Computer Science Department at Princeton University* (http://www.cs.princeton.edu)

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

Applicaitons4(2), 1994, pp. 53-62.