Point location among hyperplanes and unidirectional ray-shooting (Q1330461)

An algorithm for locating a query point in an arrangement of hyperplanes in \(d\)-dimensional space is presented. Besides having better space complexity it differs from previously known algorithms also in that if a direction is chosen ahead of time, then the first hyperplane hit by shooting the query point in that direction can be found at no extra cost. Techniques used to obtain such result include probabilistic form of divide-and-conquer and its derandomization. By bootstrapping and mixing four intermediate solutions the final one is obtained.