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 ...

Any links that help my understanding the problem better are appreciable ... If possible please give a sample code to perform the above...

Answer 1

It looks like O(n^3) to me. A simple algo might be something like:

for each pair of points
    for each of 3 possible squares which might be formed from these two points
        test remaining points to see if they coincide with the other two vertices

Answer 2

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).

Answer 3

Just a thought: if a vertex A is one corner of a square, then there must be vertices B, C, D at the other corners with AB = AD and AC = sqrt(2)AB and AC must bisect BD. Assuming every vertex has unique coordinates, I think you can solve this in O(n^2) with a hash table keying on (distance, angle).