Finding the squares in a plane given n points

Question

Given n points in a plane , how many squares can be formed ...??

I tried this by calculating the distances between each 2 points , then sort them , and look for the squares in the points with four or more equal distances after verifying the points and slopes.

But this looks like an approach with very high complexity . Any other ideas ...??

I thought dynamic programming for checking for line segments of equal distances might work ... but could not get the idea quite right ....

Any better ideas???

P.S : The squares can be in any manner . They can overlap , have a common side, one square inside another ...

If possible please give a sample code to perform the above...

Answer 1

Let d[i][j] = distances between points i and j. We are interested in a function count(i, j) that returns, as fast as possible, the number of squares that we can draw by using points i and j.

Basically, count(i, j) will have to find two points x and y such that d[i][j] = d[x][y] and check if these 4 points really define a square.

You can use a hash table to solve the problem in O(n^2) on average. Let H[x] = list of all points (p, q) that have d[p][q] = x.

Now, for each pair of points (i, j), count(i, j) will have to iterate H[ d[i][j] ] and count the points in that list that form a square with points i and j.

This should run very fast in practice, and I don't think it can ever get worse than O(n^3) (I'm not even sure it can ever get that bad).