How to make sure that a given set of points lie on the boundary of a possible square?

Question

Given a set of integral coordinates , check whether all the points given lie on side of a possible square such that axis of the square so formed lie parallel to both X-axis and Y-axis .

Suppose points are (0,0) , (1,1) , (2,2) . Answer is not possible .

Suppose points are (0 , 0) , (0,2) , (0,5) , (0,7) , (3,0) Answer is square is possible and minimum length of the side is 7 .

I tried it and came up with many corner cases and it seemed impossible to tackle them individually . I was wondering if anyone can give a more generalised approach towards this kind of problem and how to think in the right direction . Thanks in advance .

Answer 1

Let $\displaystyle x_1 = \min_{(x,y) \in P}{x}$, $\displaystyle x_2 = \max_{(x,y) \in P}{x}$, $\displaystyle y_1 = \min_{(x,y) \in P}{y}$ and $\displaystyle y_2 = \min_{(x,y) \in P}{y}$, where $P$ is the set of points (which I'm assuming to be finite). Consider the (possibly degenerate) rectangle $R$ given by the lines $y = x_1$, $y = x_2$, $x = y_1$ and $x = y_2$.

Now we consider the following two cases:

1. $x_1 = x_2$ or $y_1 = y_2$: that is, all points lie on a line. There are infinite squares satisfying the conditions; choose any segment passing through them and form a square from this segment. If you want the side to be minimal, in the case $x_1 = x_2$, choose its endpoints to be $(x_1, \bar y)$ and $(x_2, \bar y)$, where $\bar y$ is the common $y$ coordinate of all points. The case $y_1 = y_2$ is analogous.

2. $x_1 \neq x_2$ and $y_1 \neq y_2$: in this case, for a square to exist, these two conditions must hold:

   • $R$ needs to be a square, that is $x_2 - x_1 = y_2 - y_1$ (= square length).
   • each point $(x, y)$ has to satisfy the condition $$x = x_1 \lor x = x_2 \lor y = y_1 \lor y = y_2$$

Answer 2

Let $X=\{(x_i,y_i)\,\mid\,1\le i\le n\}$ be a collection of $n$ points in the plane. If the points lie on a square with sides parallel to the $x$-axis and $y$-axis, then either the $x_i$'s take on at most 2 distinct values in $X$ and/or the $y_i$'s take on at most 2 distinct values in $X$.

If both the $x_i$'s and $y_i$'s take on more than two distinct values in $X$, then there can be no one square on which all the points lie.

However this is only a necessary condition. These points could lie on a rectangle. In order to avoid this, suppose the $x$ coordinate is the one that takes on at most 2 distinct values. We must have $$ \max_{1\le i\le n}(y_i)-\min_{1\le i\le n}(y_i)=x_2-x_1 $$ otherwise the points will lie on a rectangle!