DIVIDING AND CONQUERING THE SQUARE

A local minimum of a matrix is a cell whose value is smaller than thos e of its four adjacent cells. For an n x n square matrix, we find a lo cal minimum with at most 2.554n queries, and prove a lower bound of sq uare-root 2n queries required by any method. For a different neighborh ood corresponding to the eight possible moves of a chess king, we prov e upper and lower bounds of 3n + O(log n) and 2n, respectively.