Hi, I stumbled across a simple question:
Given $$$4 \le N \le 1000$$$ points on a cartesian plane, count the number of squares where the corner of each squares lie on the points.
The first obvious method would be to put all the points in a map, and perform an $$$O(N^3)$$$ solution to find the last corner point and see if it exists.
The next method would be to find opposite corner points in $$$O(N^2)$$$ time and check if the rest of the two points exist.
Lastly, I was wondering if there's an $$$O(N\log N)$$$ solution or $$$O(N)$$$ solution?
In my opinion, the lower bond of this question is $$$O(N \sqrt{N})$$$, although the "proof" is not very solid;
I assume in one "check" we can only count 1 square, so assume we have $$$m^2$$$ points from $$$(1,1)$$$ to $$$(m,m)$$$, there will be about $$$\frac{m (m-1) (2m-1)}{6}$$$ squares. so N points can bring about $$$\frac{N \sqrt{N}}{3}$$$ squares.
but maybe there is a way to "add" multiple squares in one "check"...
update: according to https://oeis.org/A051602 the lower bond is $$$O(N^2)$$$ because the number of squares is $$$O(N^2)$$$
What about if we need to just count squares whose sides are perpendicular and parallel to x-axis and y-axis, then what could be optimization to bring complexity down from O(n^2)
I believe this can be done in $$$O(n\sqrt{n})$$$.
First, you group the points by their $$$x$$$ coordinates. Then, consider some $$$x$$$ coordinate and call it $$$x_0$$$. There are two cases
Checking if a square exists given our points can be done in $$$O(1)$$$ using a hashmap. Then it’s easy to see that the total complexity and also upper bound on the answer is $$$O(n\sqrt{n})$$$.