Finding orthogonal vectors in discrete structures

Hopcroft's problem in d dimensions asks: given n points and n hyperplanes in Rd, does any point lie on any hyperplane? Equivalently, if we are given two sets of n vectors each in Rd+1, is there a pair of vectors (one from each set) that are orthogonal? This problem has a long history and a multitude of applications. It is widely believed that for large d, the problem is subject to the curse of dimensionality: all known algorithms need at least f(d) · n2-1/O(d) time for fast-growing functions f, and at the present time there is little hope that a n2-ε · poly(d) time algorithm will be found.