C Program to detect right angled triangles

Question

If I am given 100 points in the coordinate system, and I have to find if there exist a right angled triangle in those vertices. Is there a way that I can detect the right angled triangle among those vertices without having to choose all pairs of 3 vertices and then applying Pythagoras theorem on them?? Can there be a better algorithm for this? Thanks for any help. :)

Answer 1

Here's an O(n^2 log n)-time algorithm for two dimensions only. I'll describe what goes wrong in higher dimensions.

Let S be the set of points, which have integer coordinates. For each point o in S, construct the set of nonzero vectors V(o) = {p - o | p in S - {o}} and test whether V(o) contains two orthogonal vectors in linear time as follows.

Method 1: canonize each vector (x, y) to (x/gcd(x, y), y/gcd(x, y)), where |gcd(x, y)| is the largest integer that divides 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 putting a fraction in lowest terms.) The key fact about two dimensions is that, for each nonzero vector, there exists exactly one canonical vector orthogonal to that vector, specifically, the canonization of (-y, x). Insert the canonization of each vector in V(o) into a set data structure and then, for each vector in V(o), look up its canonical orthogonal mate in that data structure. I'm assuming that the gcd and/or set operations take time O(log n).

Method 2: define a comparator on vectors as follows. Given vectors (a, b), (c, d), write (a, b) < (c, d) if and only if

s1 s2 (a d - b c) < 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 the vectors using this comparator. (This is very similar to comparing the fraction a/b with c/d.) For each vector (x, y) in V(o), binary search for its orthogonal mate (-y, x).

In three dimensions, the set of vectors orthogonal to the unit vector along the z-axis is the entire x-y-plane, and the equivalent of canonization fails to map all vectors in this plane to one orthogonal mate.