<p><strong>Decision Problem</strong></p>
<p>Input: An <span class="math-container">$m$</span> by <span class="math-container">$n$</span> Boolean matrix <span class="math-container">$M$</span>.</p>
<p>Decision Question: Does there exist a square block within <span class="math-container">$M$</span> such that upper-left corner entry == upper-right corner entry == lower-left corner entry == lower-right corner entry == 1?  That is, all four corners of the square block are 1's.</p>
<p><strong>Cubic Time Solution</strong></p>
<p>We know that this problem can be solved in <span class="math-container">$O(m \cdot n \cdot min\{m,n\})$</span> time.  The approach involves scanning through the matrix row by row.  For each row, for each pair of 1's in that row, we check whether those 1's form an edge of a square block whose four corners are 1's.</p>
<p><strong>Our Question</strong></p>
<p>What is the time complexity of this problem?  Is there a quadratic time solution?  In particular, can we solve this decision problem in <span class="math-container">$O(m \cdot n)$</span> time?</p>
<p><strong>Extra Background</strong></p>
<ol>
<li><p>If you're just looking for a rectangular block whose four corners are ones, this can be solved in <span class="math-container">$O(m \cdot n)$</span> time.  Many variations to this problem can be solved in <span class="math-container">$O(m \cdot n)$</span> time as well.  I co-authored a paper on this subject.</p>
</li>
<li><p>The paper <a href="https://doi.org/10.1007/BF01931281" rel="noreferrer">&quot;Finding squares and rectangles in sets of points&quot;</a> investigates a related problem from computational geometry where you're given a set of points in a 2D plane and you want to know if there are four points that form an axis-parallel square.</p>
</li>
</ol>
<p>Written together with Eevvoor.</p>

CC BY-SA 4.0
2020-09-19T03:41:18.727Z
You can assume wlog that $m \leq n$ (otherwise transpose) and that $n \leq 2m$ since otherwise you can cover the matrix by $2n/m$ matrices of size $m \times 2m$ that cover all square blocks. So wlog the input matrix is square $n$ by $n$.
daniello
CC BY-SA 4.0
2020-09-19T08:08:09.773Z
@daniello Yes!  That's a good point.  When the input matrix is rectangular, we can reduce it to the case where the input matrix is square.  Thank you.  :)
Michael Wehar
CC BY-SA 4.0
2020-09-19T15:32:40.810Z
Seems a little similar to finding a triangle in a graph. If you get a subcubic reduction from that problem that'd be the end of the story for now.
Joshua Grochow
CC BY-SA 4.0
2020-09-19T16:29:13.480Z
@JoshuaGrochow Yes, when searching for a rectangular block, the problem is related to finding a four cycle in a graph which is solvable in quadratic time.  However, when searching for a square block, I don't know what can be done.  Maybe there is a way to reduce triangle finding to this problem.
Michael Wehar
CC BY-SA 4.0
2020-09-22T16:38:47.087Z
This is more dead end than answer, but: there exist sets of $mn^{1-o(1)}$ nonzeros with no square, formed by filling diagonals according to a near-linear-size progression-free set (https://en.wikipedia.org/wiki/Salem%E2%80%93Spencer_set). So an algorithm that answers yes if dense enough to force a square and switches to the naive O(nonzeros times min(m,n)) otherwise can't be strongly subcubic.
David Eppstein
CC BY-SA 4.0
2020-09-22T17:22:35.907Z
@DavidEppstein I wasn't quite sure how many 1's there could be without forcing there to be a square block so this is very helpful!  User whosyourjay showed a construction related to affine planes on how many 1's there could be without forcing there to be a rectangular block whose corners are 1's. If I recall correctly, the near-tight bound was something like $m \cdot n^{1/2}$ (it had degree 3/2).
Michael Wehar
CC BY-SA 4.0
2020-09-25T21:25:12.907Z
Even if you restrict the search to right isosceles triangles, it seems impossible to have an $O(mn)$ algorithm
Marzio De Biasi
CC BY-SA 4.0
2020-09-26T08:31:14.433Z
@MarzioDeBiasi I thought about your right isosceles triangle problem. Just to confirm, this problem is asking for a square block where upper-left corner entry == upper-right corner entry == lower-left corner entry == 1, but we don't care whether lower-right corner entry is 0 or 1? I think that I have some potentially promising ideas for this problem. I'm going to try to formalize the ideas and I hope to share in a few days. Thanks again!
Michael Wehar
CC BY-SA 4.0
2020-09-26T09:11:57.060Z
@michaelwehar my idea of right triangle is a square with three 1s on the corners (no matter where the missing one is) but there is a reduction from mine to yours, where the missing one is in the bottom right (just rotate 90 and replicate four times). BTW there are some works both on monochromatic square and triangle free grids (somewhat related if you interpret "colors" with small monochromatic (sub)boxes with 1s on the diagonal)
Marzio De Biasi
CC BY-SA 4.0
2020-09-26T16:24:24.943Z
@MarzioDeBiasi Please feel welcome to share these works!  I think they could be pretty helpful.  :)
Michael Wehar
CC BY-SA 4.0
2020-10-23T05:38:07.140Z
@MarzioDeBiasi I guess that the right isosceles triangle problem is reducible to triangle finding.  We can convert the matrix to a graph where vertices are rows, columns, and diagonals.  Also, entries with 1's are associated with edges.  But, can we do any better than matrix multiplication time?
Michael Wehar
CC BY-SA 4.0
2020-10-23T21:10:52.347Z
@MarzioDeBiasi It turns out that my reduction doesn't quite work.  I'm seeing if I can fix it.
Michael Wehar
CC BY-SA 4.0
2020-10-24T21:28:01.643Z
@MichaelWehar: ok, let me know if you make some progress!
Marzio De Biasi
CC BY-SA 4.0
2022-01-04T06:31:16.530Z
It feels somehow like an FFT would help, although I haven't been able to puzzle out details. You're looking for something translation-invariant, and working in frequency space often helps with that sort of thing. Tossing out this comment in case someone else can spot something.
TLW
<ds.algorithms><matrices><computational-geometry><search-problem><boolean-matrix>
In an $m$ by $n$ Boolean matrix, can you find a square block whose four corners are ones in $O(m \cdot n)$ time?
Michael Wehar
# In an $m$ by $n$ Boolean matrix, can you find a square block whose four corners are ones in $O(m \cdot n)$ time?

(Asked by: username_0 on 2020-09-18)

**Decision Problem**

Input: An $m$ by $n$ Boolean matrix $M$.

Decision Question: Does there exist a square block within $M$ such that upper-left corner entry == upper-right corner entry == lower-left corner entry == lower-right corner entry == 1? That is, all four corners of the square block are 1's.

**Cubic Time Solution**

We know that this problem can be solved in $O(m \cdot n \cdot min\{m,n\})$ time. The approach involves scanning through the matrix row by row. For each row, for each pair of 1's in that row, we check whether those 1's form an edge of a square block whose four corners are 1's.

**Our Question**

What is the time complexity of this problem? Is there a quadratic time solution? In particular, can we solve this decision problem in $O(m \cdot n)$ time?

**Extra Background**

1. If you're just looking for a rectangular block whose four corners are ones, this can be solved in $O(m \cdot n)$ time. Many variations to this problem can be solved in $O(m \cdot n)$ time as well. I co-authored a paper on this subject.
2. The paper ["Finding squares and rectangles in sets of points"](https://doi.org/10.1007/BF01931281) investigates a related problem from computational geometry where you're given a set of points in a 2D plane and you want to know if there are four points that form an axis-parallel square.

Written together with Eevvoor.

**Tags:** ds.algorithms, matrices, computational-geometry, search-problem, boolean-matrix

> **Comments:**
> **username_1**: You can assume wlog that $m \leq n$ (otherwise transpose) and that $n \leq 2m$ since otherwise you can cover the matrix by $2n/m$ matrices of size $m \times 2m$ that cover all square blocks. So wlog the input matrix is square $n$ by $n$.  
> **username_0**: @username_1 Yes!  That's a good point.  When the input matrix is rectangular, we can reduce it to the case where the input matrix is square.  Thank you.  :)  
> **username_2**: Seems a little similar to finding a triangle in a graph. If you get a subcubic reduction from that problem that'd be the end of the story for now.  
> **username_0**: @JoshuaGrochow Yes, when searching for a rectangular block, the problem is related to finding a four cycle in a graph which is solvable in quadratic time.  However, when searching for a square block, I don't know what can be done.  Maybe there is a way to reduce triangle finding to this problem.  
> **username_3**: This is more dead end than answer, but: there exist sets of $mn^{1-o(1)}$ nonzeros with no square, formed by filling diagonals according to a near-linear-size progression-free set (https://en.wikipedia.org/wiki/Salem%E2%80%93Spencer_set). So an algorithm that answers yes if dense enough to force a square and switches to the naive O(nonzeros times min(m,n)) otherwise can't be strongly subcubic.  
> **username_0**: @DavidEppstein I wasn't quite sure how many 1's there could be without forcing there to be a square block so this is very helpful!  User whosyourjay showed a construction related to affine planes on how many 1's there could be without forcing there to be a rectangular block whose corners are 1's. If I recall correctly, the near-tight bound was something like $m \cdot n^{1/2}$ (it had degree 3/2).  
> **username_4**: Even if you restrict the search to right isosceles triangles, it seems impossible to have an $O(mn)$ algorithm  
> **username_0**: @MarzioDeBiasi I thought about your right isosceles triangle problem. Just to confirm, this problem is asking for a square block where upper-left corner entry == upper-right corner entry == lower-left corner entry == 1, but we don't care whether lower-right corner entry is 0 or 1? I think that I have some potentially promising ideas for this problem. I'm going to try to formalize the ideas and I hope to share in a few days. Thanks again!  
> **username_4**: @michaelwehar my idea of right triangle is a square with three 1s on the corners (no matter where the missing one is) but there is a reduction from mine to yours, where the missing one is in the bottom right (just rotate 90 and replicate four times). BTW there are some works both on monochromatic square and triangle free grids (somewhat related if you interpret "colors" with small monochromatic (sub)boxes with 1s on the diagonal)  
> **username_0**: @MarzioDeBiasi Please feel welcome to share these works!  I think they could be pretty helpful.  :)  
> **username_0**: @MarzioDeBiasi I guess that the right isosceles triangle problem is reducible to triangle finding.  We can convert the matrix to a graph where vertices are rows, columns, and diagonals.  Also, entries with 1's are associated with edges.  But, can we do any better than matrix multiplication time?  
> **username_0**: @MarzioDeBiasi It turns out that my reduction doesn't quite work.  I'm seeing if I can fix it.  
> **username_4**: @MichaelWehar: ok, let me know if you make some progress!  
> **username_5**: It feels somehow like an FFT would help, although I haven't been able to puzzle out details. You're looking for something translation-invariant, and working in frequency space often helps with that sort of thing. Tossing out this comment in case someone else can spot something.  

---

## 0 answers

