Cutting corners (Q5916326): Difference between revisions

First of all in this paper some notions and terms are introduced: corner cut polyhedron \(P_n^d (\subset\mathbb{R}^d)\); \({\mathbb{N}^d \choose n}\) -- set of \(n\)-element subsets of \(\mathbb{N}^d\) (with nonnegative integer vectors); staircase; \({\mathbb{N}^d\choose n}_{\text{stair}}\) -- set of finite subsets of staircases from \({\mathbb{N}^d\choose n}\); staircase polytope \(Q_n^d (\subset P_n^d)\); corner cut (as specific staircase); \({\mathbb{N}^d\choose n}_{ \text{cut}}\) -- set of all \(n\)-element corner cuts. The authors examine the set \({\mathbb{N}^d \choose n}_{\text{cut}}\) of corner cuts and the corner cut polyhedron \(P_n^d\) from four points of view: polyhedral geometry, computational complexity, enumerative combinatorics and commutative algebra. Main results are: The corner cut polyhedron satisfies \(P_n^d=Q_n^d +\mathbb{R}^d_{\geq 0}\) and is hence indeed a polyhedron. The staircase polytope \(Q_n^d\) has the same vertex set as \(P_n^d\). The map \(\lambda\to \Sigma\lambda\) defines a bijection between the corner cuts and the common vertex set of \(P_n^d\) and \(Q^d_n\). There is a polynomial time algorithm for recognizing corner cuts. For fixed \(d\) one obtains \(\#{\mathbb{N}^d \choose n}_{\text{cut}}= O(n^{2d(d-1)/(d+1)})\). The computational results are translated into algorithms for the Gröbner bases theory: The normal fan of the corner cut polyhedron \(P_n^d\) equals the Gröbner fan of the vanishing ideal of the generic configuration of \(n\) points in affine \(d\)-space.