Finding an Optimal Region in One- and Two-Dimensional Arrays

摘要

Given N real weights w_1, w_2，…, w_N stored in one--dimensional array, we consider the problem for finding an optimal interval I is contained in [1, N] under certain criteria. We shall re- view efficient algorithms developed for solving such problems Un- der several optimality criteria. This problem can be naturally extended to two-dimensional case. Namely, given a N × N two- dimensional array of N~2 reals, the problem seeks to find a sub- region of the array (e.g., rectangular subarray R) that optimizes a certain objective function. We shall also review several algo- rithms for such problems. We shall also mention applications of these problems to region segmentation in image processing and to data mining.