Signotopes Induce Unique Sink Orientations on Grids

Abstract

A unique sink orientation (USO) is an orientation of the edges of a polytope in which every face contains a unique sink. For a product of simplices $\hat{I}{”}_{m-1}\times \hat{I}{”}_{n-1}$, Felsner, Gärtner and Tschirschnitz (2005) characterize USOs which are induced by linear functions as the USOs on a $(m\times n)$-grid that correspond to a two-colored arrangement of lines. We generalize some of their results to products $\hat{I}{”}^1\times \cdots \times \hat{I}{”}^r$ of $r$ simplices, USOs on $r$-dimensional grids and $(r+1)$-signotopes.

15 pages, 10 figures. An extended abstract appeared in the booklet of the 42nd European Workshop on Computational Geometry (EuroCG 2026)