History of Minimal Pairs
of Compact Convex Sets

Pairs of compact convex sets naturally arise in quasidifferential calculus of V. F. Demyanov and A. M. Rubinov as a sub- and superdifferentials of a quasidifferentiable function (see [7]) and in formulas for the the numerical evaluation of the Aumann-Integral which were recently introduced in a series of papers by R. Baier and F. Lempio (see [1], [2] and [4]) and R. Baier and E. Farkhi [3]. In the field of combinatorial convexity G. Ewald et al. [9] used for the calculation of the combinatorial Picard group of a fan an intersting construction, called virtual polytop which can also be represented as a pair of polytopes. Since in all three cases the pairs of compact convex sets are not uniquely determined, minimal representations are of special importance. A related problem to the existence of minimal pairs is the problem on the existence of reduced pairs of convex bodies which has been studied by Chr. Bauer (see [6]).

[Poznan] [Karlsruhe]

The general frame for the investigation of minimal pairs of nonempty compact convex sets is the the Radstrom -Hormander lattice over a topological vector space of pairs of nonempty compact convex sets (see [16], [30] and [34]).

X = (X, [letter tau] ) be a topological vector space and B(X) (resp. K(X)) the family of all nonempty bounded closed (resp. compact) convex subsets of X. For nonempty A,B [subset] X : A + B denotes the algebraic Minkowski and A [Minkowski sum] B the closure of A + B. For A,B [is an element of a set] K(X) : A [Minkowski sum] B = A + B. Since B(X) satisfies the order cancellation law, i.e, for A,B,C [is an element of a set] B(X) the inclusion A [Minkowski sum] B [subset] B [Minkowski sum] C implies A [subset] C, the set B(X) endowed with the sum [Minkowski sum] and K(X) with the Minkowski sum are commutative semigroups with cancellation property.

A equivalence relation on B 2(X) = B(X) [product] B(X) is given by (A,B) [equivalent] (C,D)  iff   A [Minkowski sum] D = B [Minkowski sum] C and a partial ordering by the relation: (A,B) [is less than or equal to] (C,D)  iff  A [subset] C and B [subset] D. With [A,B] the eqivalence class of (A,B) is denoted.

A pair (A,B) [is an element of] B 2(X) is called minimal if there exists no pair (C,D) [is an element of] [A,B] with (C,D) < (A,B). It is shown in [20] that for any (A,B) [is an element of] K 2(X) exists a minimal pair (Ao,Bo) [is an element of] [A,B], but this is not true for B 2(X). J. Grzybowski and R. Urbański [13] proved that there exists a class [A,B] [is an element of] B 2(co) which contains no minimal element, where co is the Banach space of all real sequences which converge to zero.

It has been shown independently by J. Grzybowski [10] and S. Scholtes [33] that for the two-dimensional case, equivalent minimal pairs of compact convex sets are uniquely determined up to translation.

This is not longer true in higher dimensions. The first counterexample for the three-dimensional case was given by J. Grzybowski [10]. Then D. Pallaschke and R. Urbański [26] constructed an example of a continuous family of equivalent minimal pairs in the three-dimensional space, which is not related by translations.

Sufficient criteria for inclusion minimality and a cutting plane algorithm for reducing pairs of compact convex sets were derived in a series of papers of  D. Pallaschke and R. Urbański.

In [38] R. Urbański studied convex pairs of compact convex sets. For three sets A,B,S K(X), let us say that S separates the sets A and B if for every a [is an element of] A and b [is an element of] B we have [a,b] [product] S [is not equal] [empty set]. Then R. Urbański [38] proved that the following statements are equivalent:   i) A [union] B is convex,   ii) A [product] B separates A and B ,   iii) A [or] B = conv(A [union] B) is a summand of   A + B.

This result gave rize to the investigation of conditional minimality: A pair (A,B) [is an element of] K 2(X) is called convex if A [union] B is a convex set and a convex pair (A,B) [is an element of] K 2(X) is called minimal convex if for any convex pair (C,D) [is an element of] [A,B] the relation (C,D) [less than or equal to] (A,B) implies that (A,B) = (C,D) .

Conditional minimal pairs have been characterized by D. Pallaschke, W.Urbańska and R. Urbański [27]. Invariants of minimal pairs of compact convex sets, as for instance the affine dimension or codimension of the union of a minimal pair, were studied in [29] and the amound of minimal pairs has been investigated by M. Wiernowolski [42].

Finally let us remark that it is possible to consider the problem pairs of convex sets in a more general frame of a commutative semigroup S which is ordered by a relation and which satifies the condition: if as [less than or equal to] bs for some s [is an element of] S, then a [less than or equal to] b. Then (a,b) [is an element of] S 2 = S [product] S corresponds to a fraction a/b [is an element of] S 2 and minimality to a relative prime representation of a/b [is an element of] S 2.


* Do minimal pairs of convex sets exist? * Are minimal pairs of compact sets unique? *
* What about convex polytops? * What are invariants of minimal pairs of convex sets? *
* How do minimal pairs of convex sets relate to fractions? *
* History of minimal pairs of convex sets *
* How did we get interested in pairs of convex sets? *
* References * Definitions *
* Home *