The structure of max–min hyperplanes

Abstract

In this article, continuing [12,13], further contributions to the theory of max–min convex geometry are given. The max–min semiring is the set R‾=R∪{±∞} endowed with the operations ⊕=max,⊗=min in R‾. A max–min hyperplane (briefly, a hyperplane) is the set of all points x=(x1,…,xn)∈R‾n satisfying an equation of the forma1⊗x1⊕…⊕an⊗xn⊕an+1=b1⊗x1⊕…⊕bn⊗xn⊕bn+1,with ai,bi∈R‾(i=1,…n+1), where each side contains at least one term, and where ai≠bi for at least one index i. The main result is a description of a hyperplane in terms of simple polyhedral blocks. As an application, one shows that the separation of max–min closed convex sets by max–min hyperplanes is not possible in general.