The structure of max-plus hyperplanes

A max-plus hyperplane (briefly, a hyperplane) is the set of all points x=(x1,…,xn)∈Rmaxn satisfying an equation of the form a1x1⊕⋯⊕anxn⊕an+1=b1x1⊕⋯⊕bnxn⊕bn+1a1x1⊕⋯⊕anxn⊕an+1=b1x1⊕⋯⊕bnxn⊕bn+1, that is, max(a1+x1,…,an+xn,an+1)=max(b1+x1,…,bn+xn,bn+1)max(a1+x1,…,an+xn,an+1)=max(b1+x1,…,bn+xn,bn+1), with ai,bi∈Rmax(i=1,…,n+1)ai,bi∈Rmax(i=1,…,n+1), where each side contains at least one term, and where ai≠biai≠bi for at least one index i  . We show that the complements of (max-plus) semispaces at finite points z∈Rnz∈Rn are “building blocks” for the hyperplanes in Rmaxn (recall that a semispace at z   is a maximal – with respect to inclusion – max-plus convex subset of Rmaxn⧹{z}). Namely, observing that, up to a permutation of indices, we may write the equation of any hyperplane H in one of the following two forms:a1x1⊕⋯⊕apxp⊕ap+1xp+1⊕⋯⊕aqxq=a1x1⊕⋯⊕apxp⊕aq+1xq+1⊕⋯⊕amxm⊕an+1,where 0⩽p⩽q⩽m⩽n0⩽p⩽q⩽m⩽n and all ai(i=1,…,m,n+1)ai(i=1,…,m,n+1) are finite, or,a1x1⊕⋯⊕apxp⊕ap+1xp+1⊕⋯⊕aqxq⊕an+1=a1x1⊕⋯⊕apxp⊕aq+1xq+1⊕⋯⊕amxm⊕an+1,where 0⩽p⩽q⩽m⩽n0⩽p⩽q⩽m⩽n, and all ai(i=1,…,m)ai(i=1,…,m) are finite (and an+1an+1 is either finite or -∞-∞), we give a formula that expresses a nondegenerate strictly affine hyperplane (i.e., with m=nm=n and an+1>-∞an+1>-∞) as a union of complements of semispaces at a point z∈Rnz∈Rn, called the “center” of H, with the boundary of a union of complements of other semispaces at z. Using this formula, we obtain characterizations of nondegenerate strictly affine hyperplanes with empty interior. We give a description of the boundary of a nondegenerate strictly affine hyperplane with the aid of complements of semispaces at its center, and we characterize the cases in which the boundary bd H of a nondegenerate strictly affine hyperplane H is also a hyperplane. Next, we give the relations between nondegenerate strictly affine hyperplanes H, their centers z  , and their coefficients aiai. In the converse direction we show that any union of complements of semispaces at a point z∈Rnz∈Rn with the boundary of any union of complements of some other semispaces at that point z  , is a nondegenerate strictly affine hyperplane. We obtain a formula for the total number of strictly affine hyperplanes. We give complete lists of all strictly affine hyperplanes for the cases n=1n=1 and n=2n=2. We show that each linear hyperplane H   in Rmaxn (i.e., with an+1=-∞an+1=-∞) can be decomposed as the union of four parts, where each part is easy to describe in terms of complements of semispaces, some of them in a lower dimensional space.