18
$\begingroup$

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.

Improve this question
$\endgroup$
14
  • 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
    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$
    – Michael Wehar
    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$
    – Joshua Grochow
    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$
    – Michael Wehar
    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$
    – David Eppstein
    Sep 22, 2020 at 16:38

0

Reset to default

Your Answer

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