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

Michael Wehar
  • 5,127
  • 1
  • 24
  • 54
  • 5
    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 Sep 19 '20 at 03:41
  • 1
    @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 Sep 19 '20 at 08:08
  • 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. – Joshua Grochow Sep 19 '20 at 15:32
  • 3
    @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 Sep 19 '20 at 16:29
  • 2
    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 Sep 22 '20 at 16:38
  • @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 Sep 22 '20 at 17:22
  • 1
    Even if you restrict the search to right isosceles triangles, it seems impossible to have an $O(mn)$ algorithm – Marzio De Biasi Sep 25 '20 at 21:25
  • @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 Sep 26 '20 at 08:31
  • 1
    @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 Sep 26 '20 at 09:11
  • @MarzioDeBiasi Please feel welcome to share these works! I think they could be pretty helpful. :) – Michael Wehar Sep 26 '20 at 16:24
  • @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 Oct 23 '20 at 05:38
  • @MarzioDeBiasi It turns out that my reduction doesn't quite work. I'm seeing if I can fix it. – Michael Wehar Oct 23 '20 at 21:10
  • 1
    @MichaelWehar: ok, let me know if you make some progress! – Marzio De Biasi Oct 24 '20 at 21:28
  • 1
    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 Jan 04 '22 at 06:31

0 Answers0