Yet Another Math Programming Consultant: Largest Empty Rotated Square: lots of trigonometry

Work in progress...

Here, I delve into the problem of finding the largest empty rotated square. Given \(n\) data points, find the largest square rotated by an angle \(\theta\), such that the square does not contain any of the points. In [1], I discussed two special cases:

an axis-aligned square (angle is 0°),
a diamond shape, which is a square rotated by 45°.

Here we focus on arbitrary angles.

1. Exogenous Angle

Here, we assume we know the rotation angle \({\color{darkblue}\theta}\) in advance.

We need to check whether a point is outside the rotated square. That is a bit difficult. So, instead, we rotate all data points by \(-{\color{darkblue}\theta}\).

We use the same data set as in [1]:

Instead of rotating our square, we rotate the data. That will result in something like:

Here, the angle is 25°.

Now, we can simply compare the new points against an axis-aligned square. This rotation by \(-{\color{darkblue}\theta}\) is implemented as follows: \[\begin{align} & {\color{darkblue}p}'_{i,x} := {\color{darkblue}p}_{i,x} \cos({\color{darkblue}\theta}) + {\color{darkblue}p}_{i,y} \sin({\color{darkblue}\theta}) \\ & {\color{darkblue}p}'_{i,y} := -{\color{darkblue}p}_{i,x} \sin({\color{darkblue}\theta}) + {\color{darkblue}p}_{i,y} \cos({\color{darkblue}\theta}) \end{align}\] These formulas can be easily derived from the standard rotation matrix [2] and using \(\sin(-x)=-\sin(x)\) and \(\cos(-x)=\cos(x)\). Now we can just try to find a large standard square, as documented in [1]. It is noted that this is just a data-manipulation step; it is not a model equation.

One complication is that we need to ensure the square is within our outer box. This is now much more complicated. We need to construct all corner points (that is easy), and then rotate them back to our original coordinate system. Let's denote by \({\color{darkred}q}_{j,c}'\) the coordinates of the four corner points in the transformed space (so \(j=1,\dots,4\)). Then rotate them back to \({\color{darkred}q}_{j,c}\) and make sure that all corner points are inside \([0,{\color{darkblue}{\mathit{maxSize}}}] \times [0,{\color{darkblue}{\mathit{maxSize}}}]\). A complete model can look like:

Exogenous Angle Model
\[\begin{align} \max\> & {\color{darkred}s} \\&{\color{darkblue}p}'_{i,x} \le {\color{darkred}x}' + {\color{darkblue}M} {\color{darkred}\delta}_{i,1} && \forall i \\&{\color{darkblue}p}'_{i,x} \ge {\color{darkred}x}' + {\color{darkred}s} - {\color{darkblue}M} {\color{darkred}\delta}_{i,2} && \forall i \\&{\color{darkblue}p}'_{i,y} \le {\color{darkred}y}' + {\color{darkblue}M} {\color{darkred}\delta}_{i,3} && \forall i \\&{\color{darkblue}p}'_{i,y} \ge {\color{darkred}y}' + {\color{darkred}s} - {\color{darkblue}M} {\color{darkred}\delta}_{i,4} && \forall i \\ & \sum_k {\color{darkred}\delta}_{i,k} = 3 && \forall i \\&{\color{darkred}q}_{j,x}' = {\color{darkred}x}' + {\color{darkred}s} {\color{darkblue}\Delta}_{j,x} && \forall j \\&{\color{darkred}q}_{j,y}' = {\color{darkred}y}' + {\color{darkred}s} {\color{darkblue}\Delta}_{j,y} && \forall j \\&{\color{darkred}q}_{j,x} ={\color{darkred}q}_{j,x}' \cos({\color{darkblue}\theta}) - {\color{darkred}q}_{j,y}' \sin({\color{darkblue}\theta}) && \forall j \\&{\color{darkred}q}_{j,y} ={\color{darkred}q}_{j,x}' \sin({\color{darkblue}\theta}) + {\color{darkred}q}_{j,y}' \cos({\color{darkblue}\theta}) && \forall j \\&{\color{darkred}q}_{j,c} \in [0, {\color{darkblue}{\mathit{maxSize}}}] \\&{\color{darkred}s} \in [0,{\color{darkblue}{\mathit{maxSize}}}] \\&{\color{darkred}\delta}_{i,k} \in \{0,1\} \\&{\color{darkblue}p}'_{i,x} := {\color{darkblue}p}_{i,x} \cos({\color{darkblue}\theta}) + {\color{darkblue}p}_{i,y} \sin({\color{darkblue}\theta}) \\&{\color{darkblue}p}'_{i,y} := -{\color{darkblue}p}_{i,x} \sin({\color{darkblue}\theta}) + {\color{darkblue}p}_{i,y} \cos({\color{darkblue}\theta}) \\&{\color{darkblue}\Delta} = \begin{pmatrix} 0 & 0 \\ 0 & 1 \\ 1 & 0 \\ 1 & 1\end{pmatrix} \end{align}\]

Exogenous Angle Model

\[\begin{align} \max\> & {\color{darkred}s}
\\&{\color{darkblue}p}'_{i,x} \le {\color{darkred}x}' + {\color{darkblue}M} {\color{darkred}\delta}_{i,1} && \forall i
\\&{\color{darkblue}p}'_{i,x} \ge {\color{darkred}x}' + {\color{darkred}s} - {\color{darkblue}M} {\color{darkred}\delta}_{i,2} && \forall i
\\&{\color{darkblue}p}'_{i,y} \le {\color{darkred}y}' + {\color{darkblue}M} {\color{darkred}\delta}_{i,3} && \forall i
\\&{\color{darkblue}p}'_{i,y} \ge {\color{darkred}y}' + {\color{darkred}s} - {\color{darkblue}M} {\color{darkred}\delta}_{i,4} && \forall i \\ & \sum_k {\color{darkred}\delta}_{i,k} = 3 && \forall i
\\&{\color{darkred}q}_{j,x}' = {\color{darkred}x}' + {\color{darkred}s} {\color{darkblue}\Delta}_{j,x} && \forall j
\\&{\color{darkred}q}_{j,y}' = {\color{darkred}y}' + {\color{darkred}s} {\color{darkblue}\Delta}_{j,y} && \forall j
\\&{\color{darkred}q}_{j,x} ={\color{darkred}q}_{j,x}' \cos({\color{darkblue}\theta}) - {\color{darkred}q}_{j,y}' \sin({\color{darkblue}\theta}) && \forall j
\\&{\color{darkred}q}_{j,y} ={\color{darkred}q}_{j,x}' \sin({\color{darkblue}\theta}) + {\color{darkred}q}_{j,y}' \cos({\color{darkblue}\theta}) && \forall j
\\&{\color{darkred}q}_{j,c} \in [0, {\color{darkblue}{\mathit{maxSize}}}]
\\&{\color{darkred}s} \in [0,{\color{darkblue}{\mathit{maxSize}}}]
\\&{\color{darkred}\delta}_{i,k} \in \{0,1\}
\\&{\color{darkblue}p}'_{i,x} := {\color{darkblue}p}_{i,x} \cos({\color{darkblue}\theta}) + {\color{darkblue}p}_{i,y} \sin({\color{darkblue}\theta})
\\&{\color{darkblue}p}'_{i,y} := -{\color{darkblue}p}_{i,x} \sin({\color{darkblue}\theta}) + {\color{darkblue}p}_{i,y} \cos({\color{darkblue}\theta})
\\&{\color{darkblue}\Delta} = \begin{pmatrix} 0 & 0 \\ 0 & 1 \\ 1 & 0 \\ 1 & 1\end{pmatrix} \end{align}\]

Notes:

\(\sin({\color{darkblue}\theta})\) and \(\cos({\color{darkblue}\theta})\) are constants. Unbelievably, this is actually a linear MIP model!
\({\color{darkred}x}',{\color{darkred}y}'\) denotes the lower-left corner of the axis-aligned square (like in [1]).
\({\color{darkred}q}_{j,c}', j=1,\dots,4\) are the four corner points (in transformed space). We map them back to \({\color{darkred}q}_{j,c}\), which form a rotated square.
Below, we plot the solution both in the transformed space and in the original coordinate system.
This is a very easy MIP:

Proven optimal solution
MIP Solution: 3.085938 (657 iterations, 0 nodes)

The solution in transformed coordinates looks like:

When we transform this back to our original coordinate system, we see: