Complexity of Parallelogram Range Minimum Query
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 &lt; 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. 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$.