# Efficient algorithm to find all 4-subsets of N points forming a square with no other points inside

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.

• I modified the body, but I can't think of any extra info that would clarify the task. What are you confused about? The problem statement seems clear to me. – D G Sep 1 '16 at 13:18
• I'm guessing $O(N^2\log N)$ is the best you can do. You need to choose two points, then search for the other two. I don't have a proof though. – Matt Samuel Sep 1 '16 at 13:29
• No point can be a vertex of more than four squares with disjoint interiors, so that $4N$ is a generous upper bound on the number of such squares that can be formed. Is it your purpose to form a tighter upper bound, or to efficiently identify the squares (or perhaps both)? – hardmath Sep 1 '16 at 13:58
• To efficiently identify the squares, though I'd be interested in a tighter upper bound too as that may help lead to a method of efficiently identifying the squares. Thanks – D G Sep 1 '16 at 14:14
• You can immediately remove the factor four from your upper bound because this way of counting counts each square four times (once for each vertex used). The upper bound $N$ on number of squares (without points in the interior) is asymptotically tight in the sense that placing $(n+1)^2$ points in a uniform Cartesian grid produces $n^2$ of the allowable squares, so ratio of squares to points tends to $1$ as $n\to \infty$. – hardmath Sep 1 '16 at 20:26