How to divide a territory? A new simple differential formalism for optimization of set functions

In many practical problems, we must optimize a set function, i.e., find a s et A for which f(A) --> max, where f is a function defined on the class of sets. Such problems appear in design, in image processing, in game theory, etc. Most optimization problems can be solved (or at least simplified) by u sing the fact that small deviations from an optimal solution can only decre ase the value of the objective function; as a result, some derivative must be equal to 0. This approach has been successfully used, e.g., for set func tions in which the desired set A is a shape, i.e., a smooth (or piece-wise smooth) surface. In some real-life problems, in particular, in the territor ial division problem, the existing methods are not directly applicable. For such problems, we design a new simple differential formalism for optimizin g-set functions. (C) 1999 John Wiley & Sons, Inc.