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 subset of [1, N] under certain criteria. We shall review efficient algorithms developed for solving such problems under several optimality criteria. This problem can be naturally extended to two-dimensional case. Namely, given a N x N two-dimensional array of N-2 reals, the problem seeks to find a subregion of the array (e.g., rectangular subarray R) that optimizes a certain objective function. We shall also review several algorithms for such problems. We shall also mention applications of these problems to region segmentation in image processing and to data mining.
optimal interval data mining combinatorial optimization inter-class variance image segmentation