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.

  • $\begingroup$ 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. $\endgroup$ – D G Sep 1 '16 at 13:18
  • $\begingroup$ 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. $\endgroup$ – Matt Samuel Sep 1 '16 at 13:29
  • $\begingroup$ 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)? $\endgroup$ – hardmath Sep 1 '16 at 13:58
  • 1
    $\begingroup$ 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 $\endgroup$ – D G Sep 1 '16 at 14:14
  • $\begingroup$ 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$. $\endgroup$ – hardmath Sep 1 '16 at 20:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.