I'm looking for an algorithm (or any useful resources) to solve the following problem:
Given a set of $N$ distinct points on a plane, find all the ways to choose $4$ of those points that are the vertices of a square and none of the other points in your set lie inside that square.
I have proved that there are at most $4N$ such squares, and I have an $O(N^2 \log N)$ algorithm to find them all. I'm not too concerned about whether the definition of inside includes points on the edge of a square.