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

Naoki KATOH  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E83-D    No.3    pp.438-446
Publication Date: 2000/03/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8532
Type of Manuscript: INVITED SURVEY PAPER
Category: Algorithms for Geometric Problems
Keyword: 
optimal interval,  combinatorial optimization,  interclass variance,  image segmentation,  data mining,  

Full Text: PDF(1.7MB)>>
Buy this Article


Summary: 
Given N real weights w1, w2, . . . , wN stored in one-dimensional array, we consider the problem for finding an optimal interval I [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 NN two-dimensional array of N2 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.

open access publishing via