Simplest function sufficient to categorize a square

51 Views Asked by At

Background Let $p_i=(x_i,y_i)$ with $i\in \{1,2,3,4\}$ define four (possibly repeating) points in the plane. Let $f(a,b,c)$ be any function with the property that

$$f(a,b,c)=f(a,c,b)=f(b,a,c)=f(b,c,a)=f(c,a,b)=f(c,b,a)$$

That is, the output of $f$ is independent on any permutations of the inputs. Finally, define

$$S_1=f(d(p_1,p_2),d(p_1,p_3),d(p_1,p_4))$$

where $d(a,b)$ is the standard Euclidean distance (although this could really be any metric). In a similar manner, define $S_2,S_3,$ and $S_4$. We say that a function $f$ categorizes a square if

$$S_1=S_2=S_3=S_4\Leftrightarrow \text{The points }p_1,p_2,p_3,p_4\text{ define a square}$$

Obviously, the $\Leftarrow$ implication is self-evident (at least if one considers four identical points a square). This leaves the question of what functions $f$ imply that the points $p$ form a square?

Question: What is the simplest such function $f$ which categorizes a square? In this question, 'simple' can be taken to mean: cleanest, neatest, easiest to compute, etc.

Work so far: The obvious choice for $f$ is

$$f(a,b,c)=a+b+c$$

By almost any definition, this is probably the simplest function which could possibly categorize a square (this is opposed to constant $f$ which definitely does not categorize the square). However, I could not prove that this function works although I can show it for the following function:

$$f(a,b,c)=\left(\frac{\max\{a,b,c\}}{\sqrt{2}}-\min\{a,b,c\}\right)^2+\left(a+b+c-\max\{a,b,c\}-2\min\{a,b,c\}\right)^2+\min\{a,b,c\}$$

This function evaluates to $\min\{a,b,c\}$ if the two shorter distances are equal and the longest distance is equal to the shorter distances after being stretched by a factor of $\sqrt{2}$.

To prove this function categorizes a square, it is sufficient to prove cases depending on how many of the lengths amongst the four points equal the absolute minimum length (in a square, its four of the lengths). Since $\binom{4}{2}=6$, one simply has to check the cases:

$$\text{There is $1$ unique minimum distance among $6$ lengths}$$

$$\text{There are $2$ equal minimum distances among $6$ lengths}$$

$$\vdots$$

$$\text{There are $5$ equal minimum distances among $6$ lengths}$$

(the case where all the distance are equal is impossible). After going through the logic, one can show that in all cases but the case with $4$ equal minimum distances that $S_i\neq S_j$ for some $i,j\in\{1,2,3,4\}$. Then in this case, you can show that this corresponds to a square.

1

There are 1 best solutions below

0
On BEST ANSWER

Fix $p_1,p_2,p_3,p_4\in\mathbb{R}^2$.

If $p_1,p_2,p_3,p_4$ are the vertices of a (possibly degenerate) rectangle, then $$ S_1=S_2=S_3=S_4 $$ holds, regardless of the choice of the symmetric function $f(a,b,c)$.

In what follows, let $f(a,b,c)=a+b+c$.

Claim:$\;$If $S_1=S_2=S_3=S_4$, then $p_1,p_2,p_3,p_4$ are the vertices of a (possibly degenerate) rectangle.

Proof:

Assume $S_1=S_2=S_3=S_4=s$.

If $s=0$, then $p_1=p_2=p_3=p_4$, in which case, $p_1,p_2,p_3,p_4$ are the vertices of a degenerate rectangle.

Next assume $s > 0$.

Without loss of generality, we can assume $s=1$.

For $1\le i < j\le 4$, let $d_{ij}=d(p_i,p_j)$

After appropriate re-indexing we have $6$ cases, exactly one of which must hold . . .

Case $(1)$:$\;p_1=p_2=p_3,\,p_3\ne p_4$.

Then from $S_1=S_2=S_3=1$ we get $d_{14}=d_{24}=d_{34}=1$, but then $S_4=3$, contradiction.

Case $(2)$:$\;p_1=p_2,\,p_3=p_4,\,p_1\ne p_3$.

Then it's immediate that $p_1,p_2,p_3,p_4$ are the vertices of a degenerate rectangle.

Case $(3)$:$\;p_1=p_2,\,p_2\ne p_3,\,p_2\ne p_4,\,p_3\ne p_4$.

Then we get $$ 2 = 2S_1 = 2d_{13}+2d_{14} < (2d_{13}+d_{34})+(2d_{14}+d_{34}) = S_3+S_4 = 2 $$ contradiction.

Case $(4)$:$\;p_1,p_2,p_3,p_4$ are distinct, but collinear.

Without loss of generality, assume $p_1,p_2,p_3,p_4$ are consecutive points on the line segment with endpoints $p_1,p_4$.

Then we get $$ S_1 = 3d_{12}+2d_{23}+d_{34} > d_{12}+2d_{23}+d_{34} = S_2 $$ contradiction.

Case $(5)$:$\;p_1,p_2,p_3,p_4$ are distinct, and $p_4\in T$, where $T$ is a non-degenerate closed triangular region with vertices $p_1,p_2,p_3$.

Without loss of generality, assume $d_{23}=\max(d_{12},d_{13},d_{23})$.

It follows that $d_{14} < d_{23}$.

Now we have \begin{align*} 3 &=\, S_1+S_2+S_3 \\[4pt] &=\, 2(d_{12}+d_{13}+d_{23})+(d_{14}+d_{24}+d_{34}) \\[4pt] &=\, 2(d_{12}+d_{13}+d_{23})+S_4 \\[4pt] &=\, 2(d_{12}+d_{13}+d_{23})+1 \\[4pt] \end{align*} hence $d_{12}+d_{13}+d_{23}=1$.

But then we get $$ 1 = S_1 = d_{12}+d_{13}+d_{14} < d_{12}+d_{13}+d_{23} = 1 $$ contradiction.

Case $(6)$:$\;p_1,p_2,p_3,p_4$ are consecutive vertices of a convex quadrilateral, $Q$ say.

From $S_1=S_3$ we get $$ d_{14}+d_{12}=d_{23}+d_{34}\qquad(\text{eq}1) $$ and from $S_2=S_4$ we get $$ d_{12}+d_{23}=d_{34}+d_{14}\qquad(\text{eq}2) $$ Subtracting $(\text{eq}2)$ from $(\text{eq}1)$ yields $$ d_{14}-d_{23}=d_{23}-d_{14} $$ hence $d_{14}=d_{23}=x$, say.

Then $(\text{eq}1)$ becomes $$ x+d_{12}=x+d_{34} $$ hence $d_{12}=d_{34}=y$, say.

Thus the opposite sides of $Q$ have equal lengths, so $Q$ is a parallelogram.

Then from $S_1=S_2$ we get $$ x+y+d_{13}=y+x+d_{24} $$ hence $d_{13}=d_{24}$, so the diagonals of $Q$ have equal lengths.

It follows that $Q$ is a rectangle.

This completes the proof.