POINT LOCATION AMONG HYPERPLANES AND UNIDIRECTIONAL RAY-SHOOTING

We present an algorithm for locating a query point q in an arrangement of n hyperplanes in R(d). The size of the data structure is O(n(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(d)/(log n) inverted right perpendicular d/2 inverted left perpendicular -epsilon), for any fixed epsilon > 0.