We present a solution to the point location problem in arrangements of hyperplanes in Ed with running time O(d5 log n) and space O(nd+κ) for arbitrary κ > 0, where n is the number of hyperplanes. The main result is the d5 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.
