Point Location Among Hyperplanes and Unidirectional Ray-Shooting
Abstract:
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.