Concave cocirculations in a triangular grid

Let G be a planar digraph embedded in the plane such that each bounded face contains three edges and forms an equilateral triangle, and let the union R of these faces be a convex polygon. We consider the polyhedral cone B(G) formed by the real-valued functions σ on the set of boundary edges of G with the following property: there exists a concave function c on R which is affinely linear within each bounded face and satisfies c(v) − c(u) = σ(e) for each boundary edge e = (u, v). Knutson, Tao and Woodward obtained a result on honeycombs which implies that if the polygon R is a triangle, then the cone B(G) is described by linear inequalities of Horn's type with respect to so-called puzzles, along with obvious linear constraints. The purpose of this paper is to give an alternative proof of that result, working in terms of discrete concave functions, rather than honeycombs. Our proof is based on a linear programming approach and a nonstandard flow model. Moreover, the result is extended to an arbitrary convex polygon R as above.