<p>This can be reduced to rectangular RMQ in <span class="math-container">$O(n^2)$</span> time and space. Create a new array <span class="math-container">$H$</span> where <span class="math-container">$H[i][i+j] := G[i][j]$</span>, padding entries <span class="math-container">$H[i][k]$</span> with <span class="math-container">$k &lt; i$</span> or <span class="math-container">$k \ge i + n$</span> with <span class="math-container">$\infty$</span>. Run <span class="math-container">$RMQ(a, b, c, d)$</span> on <span class="math-container">$H$</span> whenever you would run <span class="math-container">$RMQ_P(a, b, c, d)$</span> on <span class="math-container">$G$</span>.</p>

<p>Now run your favorite 2D-RMQ algorithm such as <a href="https://link.springer.com/chapter/10.1007/978-3-540-73437-6_29" rel="nofollow noreferrer">this</a>. Perhaps you want to be very conservative with the extra space used though. In that case I suspect unpacking your favorite result will show that it helps to avoid writing <span class="math-container">$H$</span> down, and instead use an <span class="math-container">$O(1)$</span> function to produce values of <span class="math-container">$H$</span> by lookup into <span class="math-container">$G$</span>.</p>

CC BY-SA 4.0
2019-08-13T11:03:53.327Z
Thanks, this works very nicely. I wrote some Python code: https://repl.it/repls/TransparentExaltedAngle  that tested this on a 10x10 grid of random integers on all possible queries $(a,b,c,d)$ and it passed all tests. Thanks!
user3508551
CC BY-SA 4.0
2019-08-12T23:24:27.587Z
2019-08-12T23:24:27.587Z
Whosyourjay
<p>Given an <span class="math-container">$n\times n$</span> array <span class="math-container">$G$</span>, what is known about the complexity of parallelogram static RMQs?</p>

<p>More formally, answering the query</p>

<p><span class="math-container">$$RMQ_P(a,b,c,d)=\min_{a\leq i \leq b \\ c \leq i+j \leq d}G[i][j]$$</span></p>

<p>In terms of preprocessing, and answering the query where the array is static</p>

<query-complexity><range-searching>
Complexity of Parallelogram Range Minimum Query
user3508551
# Complexity of Parallelogram Range Minimum Query

(Asked by: username_0 on 2019-08-12)

Given an $n\times n$ array $G$, what is known about the complexity of parallelogram static RMQs?

More formally, answering the query

$$RMQ\_P(a,b,c,d)=\min\_{a\leq i \leq b \\ c \leq i+j \leq d}G[i][j]$$

In terms of preprocessing, and answering the query where the array is static

**Tags:** query-complexity, range-searching


---

## 1 answers

### Answer by username_1 on 2019-08-12. Score: 2 | Accepted answer

This can be reduced to rectangular RMQ in $O(n^2)$ time and space. Create a new array $H$ where $H[i][i+j] := G[i][j]$, padding entries $H[i][k]$ with $k < i$ or $k \ge i + n$ with $\infty$. Run $RMQ(a, b, c, d)$ on $H$ whenever you would run $RMQ\_P(a, b, c, d)$ on $G$.

Now run your favorite 2D-RMQ algorithm such as [this](https://link.springer.com/chapter/10.1007/978-3-540-73437-6_29). Perhaps you want to be very conservative with the extra space used though. In that case I suspect unpacking your favorite result will show that it helps to avoid writing $H$ down, and instead use an $O(1)$ function to produce values of $H$ by lookup into $G$.

> **Comments:**
> **username_0**: Thanks, this works very nicely. I wrote some Python code: https://repl.it/repls/TransparentExaltedAngle  that tested this on a 10x10 grid of random integers on all possible queries $(a,b,c,d)$ and it passed all tests. Thanks!  

---

