Here O (n ^ 2 log n) -time for only two dimensions . I will describe what goes wrong in higher dimensions.
Let S be the set of points that have integer coordinates. For each point o in S, we construct the set of nonzero vectors V (o) = {p - o | p in S - {o}} and check if V (o) contains two orthogonal vectors in linear time as follows.
Method 1: canonicalize each vector (x, y) to (x / gcd (x, y), y / gcd (x, y)), where | gcd (x, y) | is the largest integer dividing both x and y, and where gcd (x, y) is negative if y is negative, positive if y is positive, and | x | if y is zero. (This is very similar to including a fraction in the lower terms.) The key fact of the two dimensions is that for each nonzero vector there is exactly one canonical vector orthogonal to this vector, in particular, the canonization (-y, x). Insert the canonization of each vector in V (o) into the data structure of the set, and then for each vector in V (o) find the canonical orthogonal pair in the frame in this data structure. I assume that gcd and / or set operations take O (log n) time.
Method 2: determine the comparator by vectors as follows. Given the vectors (a, b), (c, d) , write (a, b) < (c, d) if and only if
s1 s2 (ad - bc) < 0,
Where
s1 = -1 if b < 0 or (b == 0 and a < 0) 1 otherwise s2 = -1 if d < 0 or (d == 0 and c < 0) 1 otherwise.
Sort vectors using this comparator. (This is very similar to comparing the fraction of a/b with c/d .) For each vector (x, y) in V (o), the binary search for its orthogonal conjugation (-y, x).
In three dimensions, the set of vectors orthogonal to a unit vector along the z axis represents the entire xy plane, and the canonization equivalent does not map all vectors in this plane onto one orthogonal mat.