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" 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.

  • 5
    $\begingroup$ 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$. $\endgroup$
    – daniello
    Commented Sep 19, 2020 at 3:41
  • 1
    $\begingroup$ @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. :) $\endgroup$ Commented Sep 19, 2020 at 8:08
  • 2
    $\begingroup$ 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. $\endgroup$ Commented Sep 19, 2020 at 15:32
  • 3
    $\begingroup$ @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. $\endgroup$ Commented Sep 19, 2020 at 16:29
  • 2
    $\begingroup$ 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 (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. $\endgroup$ Commented Sep 22, 2020 at 16:38


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.