2D Local Maximum (Peak Finding)

Context: FIT2004_MOC · Applied 2 Problem 6 — the Divide and Conquer exercise where the naive halving is not aggressive enough, and the correctness argument (not the code) carries the marks. Parent Framework: Divide and Conquer

Quick Revision

• 🎯 Objective: in an $n\times n$ matrix of distinct numbers, return the coordinates of any element larger than its (2–4) orthogonal neighbours ➔ in $\Theta (n)$ worst case.
• 📦 Core Components: scan a window frame (first/middle/last row $+$ column) $\Theta (n)$ ➔ its max $x$ is a peak, or a neighbour $y>x$ lies in one quadrant ➔ recurse into that quadrant, which is $\frac{n}{2}\times \frac{n}{2}$.
• ⚡ Key Constraint: $\Theta (n)$ on an input of $n^2$ cells means the algorithm cannot read most of the matrix — so the subproblem must shrink in both dimensions. Halving one axis leaves the per-call scan at $\Theta (n)$ forever and costs $\Theta (n\log n)$.

📝 How It Works

1. Why the two obvious algorithms fail their bound

• Gradient ascent is $\Theta (n^2)$ ➔ repeatedly step to the largest neighbour. It terminates (values strictly increase, the grid is finite) but a snake-shaped ridge makes it traverse half the matrix — matrix 1 of the sheet starting from the top-left is exactly that adversary.
• Splitting on the middle column alone is $\Theta (n\log n)$ ➔ deciding which side to keep costs a $\Theta (n)$ column scan, and the sub-matrix is $n\times \frac{n}{2}$ — the column never gets shorter. The level-sum is $\Theta (n)$ repeated ${\log }_{2}n$ times, with no geometric decay.
• The diagnostic ➔ a $T(n)=T(n/2)+\Theta (n)$ target requires the per-call work itself to halve; only cutting both axes achieves that ➔ Solving Recurrences (Telescoping), the $r=\frac{1}{2}$ root-dominated regime.

2. The cross method and its correctness argument

• Step 1 — scan the cross ➔ take the middle row and middle column ($2n-1$ cells, $\Theta (n)$) and let $x$ be their maximum.
• Step 2 — test $x$ ➔ if $x$ beats its four neighbours, return its coordinates; done.
• Step 3 — follow the escape ➔ otherwise some neighbour $y>x$ exists, and $y$ must lie off the cross (everything on it is $\le x$) ⟹ $y$ sits in one of the four quadrants the cross carves out.
• Step 4 — recurse into that quadrant $A$ ➔ size $\approx \frac{n}{2}\times \frac{n}{2}$.
• ⚡ The correctness claim ➔ $A$ is guaranteed to contain a local maximum of the whole matrix $M$. Run gradient ascent from $y$: values strictly increase every step, and every cross cell is $<y$, so the walk can never cross back over the cross; the grid is finite, so it halts at a peak, and that peak is inside $A$. Discarding three quadrants therefore discards nothing that was needed.

3. The window-frame repair

• The bug in plain cross recursion ➔ the max $z$ of a sub-matrix’s cross may beat its neighbours within the sub-matrix yet lose to a cell just outside it. Sheet witness: at recursion level 2 of matrix 2, $340$ beats its sub-matrix neighbours $260,235,305$ but is crushed by $503$, which belonged to the previous level’s cross.
• The fix ➔ scan a window frame: the first, middle and last rows plus the first, middle and last columns of the current sub-matrix, and maximise over all six lines.
• Why it works ➔ the frame includes the sub-matrix boundary, so the winner is compared against cells that border the outside world; nothing beyond the frame can quietly dominate it.
• Cost is unchanged ➔ $6$ lines of length $\le n$ is still $\Theta (n)$, so the recurrence and the $\Theta (n)$ bound survive.

⚖️ Complexity

Approach	Recurrence	Best / Average / Worst	Auxiliary space	Why it lands there
Gradient ascent (walk uphill)	—	$\Theta (1)$ / — / $\Theta (n^2)$	$O(1)$	a ridge forces a traversal of half the cells
Middle-column split	$T(n)=T(n/2)+\Theta (n)$ per call, $n$ fixed	$\Theta (n\log n)$ all	$\Theta (\log n)$ frames	column length never shrinks ⟹ ${\log }_{2}n$ scans of cost $\Theta (n)$
Cross / window frame	$T(n)=T(n/2)+\Theta (n)$	$\Theta (n)$ all	$\Theta (\log n)$ frames	$r=a/b=\frac{1}{2}<1$ ⟹ root-dominated

$T(n)=T(n/2)+cn=cn{\sum }_{i=0}^{{\log }_{2}n}{\left(\frac{1}{2}\right)}^i<2cn=\Theta (n)$

When It Flips: the entire $\Theta (n\log n)\to \Theta (n)$ gain comes from the second axis, not from a cleverer scan. The two variants perform identical work at the root; they diverge because only the cross version makes level $i$ cost $cn/2^i$, turning the level sum from an arithmetic repetition into a convergent Geometric Series.

📊 Exam Execution Trace

On sheet matrix 1 ($7\times 7$, $0$-indexed). Every neighbour test is made against the ORIGINAL matrix $M$, never against the sub-matrix — that is the window-frame discipline:

Step	Sub-matrix	Frame max $x$ (position)	Beaten by?	Action
0 (Init)	rows $\mathrm{0..6}$, cols $\mathrm{0..6}$	$46$ at $(3,6)$	$47$ at $(2,6)$	recurse into the quadrant holding $(2,6)$
1	rows $\mathrm{0..2}$, cols $\mathrm{4..6}$	$48$ at $(1,6)$	$49$ at $(0,6)$	recurse into the quadrant holding $(0,6)$
2	row $0$, col $6$	$49$ at $(0,6)$	none ($48$ below, $30$ left)	return $(0,6)$

Read-off: three levels, scans of length $\approx 7,3,1$ — the halving of the scan is the whole point; a column-only split would have scanned $7$ cells at every level.

⚠️ Common Mistakes

• 💡 Claiming $\Theta (n)$ is impossible because the input has $n^2$ cells ➔ reading the whole input is only mandatory when the answer depends on every cell. A peak is a local property, so the algorithm legitimately certifies an answer after touching $\Theta (n)$ cells.
• 💡 Recursing into the quadrant with the largest cross value instead of the one containing $y$ ➔ the correctness argument is built on $y$ specifically ($y>x\ge$ every cross cell); any other quadrant carries no such guarantee and the recursion can return a non-peak.
• 💡 Comparing against sub-matrix neighbours ➔ the $340$-vs-$503$ failure. A candidate must be tested against its neighbours in $M$; the frame exists precisely to make that test meaningful.
• 💡 Assuming a unique peak ➔ the spec asks for any local maximum. Arguments that quietly rely on there being one global answer prove nothing, and multiple peaks is the normal case.

🧠 Active Recall

Splitting on the middle column halves the matrix every call, yet the algorithm is $\Theta (n\log n)$ rather than $\Theta (n)$. Where does the argument break?

• Hint: Write out the per-level work, not the per-level subproblem count.

Answer

• Short answer: the sub-matrix is $n\times \frac{n}{2}$, so the deciding scan is a full-length column at every level — the work is $\Theta (n)$ for all ${\log }_{2}n$ levels, summing to $\Theta (n\log n)$.
• Why: Only shrinking work sums geometrically ➔ $T(n)=T(n/2)+\Theta (n)$ collapses to $\Theta (n)$ only when the $\Theta (n)$ shrinks with the argument. Halving one axis halves the cell count but not the scan length, so the $r=\frac{1}{2}$ decay never starts.

Justify discarding three of the four quadrants after finding a neighbour $y>x$.

• Hint: Imagine walking uphill from $y$ and ask what would have to happen to escape.

Answer

• Short answer: a strictly-increasing walk from $y$ cannot re-enter the cross (every cross cell is $\le x<y$), and a finite grid of distinct values makes the walk terminate — so a peak of $M$ exists inside the quadrant holding $y$.
• Why: The cross is a one-way barrier ➔ $x$ is the cross maximum, so leaving the quadrant would require stepping down, which uphill movement forbids. The argument certifies existence without locating the peak, which is exactly what a D&C correctness proof needs.

Why replace the cross with a window frame, given both cost $\Theta (n)$?

• Hint: Ask what a sub-matrix does not know about itself.

Answer

• Short answer: without the boundary rows and columns, a sub-matrix’s local winner may be beaten by a cell just outside it (the sheet’s $340$ against $503$), so the algorithm can return a non-peak.
• Why: Correctness needs the boundary in scope ➔ including the first and last rows/columns makes the recursion’s candidate comparable against cells outside the sub-matrix, restoring the invariant “the reported cell beats its neighbours in $M$“. Six lines instead of two is a constant factor, so the $\Theta (n)$ bound is untouched.