Zigzags in thin chamber complexes are investigated, in particular, all zigzags in the Coxeter complexes are described. Using this description, we show that the lengths of all zigzags in the simplex $$\alpha _{n}$$ , the cross-polytope $$\beta _{n}$$ , the 24-cell, the icosahedron and the 600-cell are equal to the Coxeter numbers of $$\mathsf{A}_{n}$$ , $$\mathsf{B}_{n}=\mathsf{C}_{n}$$ , $$\mathsf{F}_{4}$$ and $$\mathsf{H}_{i}$$ , $$i=3,4$$ , respectively. We also discuss in which cases two faces in a thin chamber complex can be connected by a zigzag.

A polyhedral norm is a norm N on R^n for which the set N(x)\leq 1 is a polytope. This covers the case of the L^1 and L^{\infty} norms. We consider here effective algorithms for determining the Voronoi polytope for such norms with a point set being a lattice. The algorithms, that we propose, use the symmetries effectively in order to compute a decomposition of the space into convex polytopes named {\em $VN$-spaces}. The Voronoi polytopes and other geometrical information are easily obtained from it.

Abstract A finite metric (or more properly semimetric) on n points is a nonnegative vector d = (dij) 1 ⩽ i < j ⩽ n that satisfies the triangle inequality dij ⩽ dik + djk. The L1 (or Manhattan) distance ‖x − y‖1 between two vectors x = (xi) and y = (yi) in Rm is given by ‖x − y‖1 = ∑1⩽i⩽m |xi − yi|. A metric d is L1‐embeddable if there exist vectors z1, z2,…, zn in Rm for some m, such that dij = ‖zi − zj‖1 for 1 ⩽ i < j ⩽ n. A cut metric is a metric with all distances zero or one and corresponds to the incidence vector of a cut in the complete graph on n vertices. The cut cone Hn is the convex cone formed by taking all nonnegative combinations of cut metrics. It is easily shown that a metric is L1‐embeddable if and only if it is contained in the cut cone. In this expository paper, we provide a unified setting for describing a number of results related to L1‐embeddability and the cut cone. We collect and describe results on the facial structure of the cut cone and the complexity of testing the L1‐embeddability of a metric. One of the main sections of the paper describes the role of L1‐embeddability in the feasibility problem for multi‐commodity flows. The Ford and Fulkerson theorem for the existence of a single commodity flow can be restated as an inequality that must be valid for all cut metrics. A more general result, known as the Japanese theorem, gives a condition for the existence of a multicommodity flow. This theorem gives an inequality that must be satisfied by all metrics. For multicommodity flows involving a small number of terminals, it is known that the condition of the Japanese theorem can be replaced with one of the Ford–Fulkerson type. We review these results and show that the existence of such Ford–Fulkerson‐type conditions for flows with few terminals depends critically on the fact that certain metrics are L1‐embeddable.