The structure of max-plus hyperplanes

A coax-plus hyperplane (briefly, a hyperplane) is the set of all points x = (x(1)..., x(n)) epsilon R-max(n) satisfying an equation of the form a(1)x(1) circle plus...circle plus a(n) x(n) circle plus a(n+1) = b(1)x(1) circle plus...circle plus b(n)x(n) circle plus b(n+1), that is, max(a(1) + x(1),..., a(n) + x(n), a(n+1)) = max(b(1) + x(1),..., b(n) + x(n), b(n+ l)), with a(i), b(i) epsilon R-max (i = 1,..., n + 1),where each side contains at least one term, and where a(i) not equal b(i) for at least one index i. We show that the complements of (max-plus) semispaces at finite points z epsilon R-n are "building blocks" for the hyperplanes in R-max(n) (recall that a semispace at z is a maximal - with respect to inclusion - max-plus convex subset of R-max(n)\(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: a(1)x(1) circle plus...circle plus a(p) x(p) a(p+1)x(p+1) circle plus...circle plus a(q) x(q) = a(1)x(1) circle plus...circle plus a(p)x(p) a(q+1)x(q+1) circle plus...circle plus a(m)x(m) circle plus a(1)x(1) circle plus...circle plus a(n) x(n), where 0 <= p <= q <= m <= n and all a(i) (i = I,..., m, n + 1) are finite, or, a(1)x(1) circle plus...circle plus a(p) x(p) a(p+1)x(p+1) circle plus...circle plus a(q) x(q) circle plus a(n+1) = a(1)x(1) circle plus...circle plus a(p)x(p) circle plus...circle plus a(q+1)x(q+1)circle plus...circle plus a(m)x(m) a(n+1) x(n+1), where 0 <= p <= q <= m <= n, and all a(i) (i = 1,..., m) are finite (and a(n+1) is either finite or -infinity), we give a formula that expresses a nondegenerate strictly affine hyperplane (i.e., with m = n and a(n+1) > -infinity) as a union of complements of setnispaces at a point z epsilon R-n 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 a(i). In the converse direction we show that any union of complements of semispaces at a point z epsilon R-n 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 = 1 and n = 2. We show that each linear hyperplane H in R-max(n) (i.e., with a(n+l) = -infinity) 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. (c) 2007 Elsevier Inc. All rights reserved.