Point location in arrangements of hyperplanes. (English) Zbl 0781.68121
Summary: We present a solution to the point location problem in arrangements of hyperplanes in \(E^ d\) with running time \(O(d^ 5\log n)\) and space \(O(n^{d+\kappa})\) for arbitrary \(\kappa>0\), where \(n\) is the number of hyperplanes. The main result is the \(d^ 5\) factor in the expression for the running time. All previously known algorithms are exponential in \(d\) or \(\log n\). This leads to nonuniform polynomial algorithms for NP- complete problems.
MSC:
68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
68Q25 | Analysis of algorithms and problem complexity |