×

Cutting corners. (English) Zbl 0955.52008

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.

MSC:

52B05 Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.)
52B12 Special polytopes (linear programming, centrally symmetric, etc.)
52B55 Computational aspects related to convexity
68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
05A99 Enumerative combinatorics
14A10 Varieties and morphisms
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[2] Alon, N.; Onn, S., Separable partitions, Discrete Appl. Math., 91, 39-51 (1999) · Zbl 0926.05011
[3] Andrews, G., A lower bound for the volume of strictly convex bodies with many boundary points, Trans. Amer. Math. Soc., 106, 270-273 (1965) · Zbl 0118.28301
[4] Bárány, I.; Vershik, A., On the number of convex lattice polytopes, Geom. Funct. Anal., 2, 381-393 (1992) · Zbl 0772.52010
[5] Bayer, D.; Stillman, M., A criterion for detecting \(m\)-regularity, Invent. Math., 87, 1-11 (1987) · Zbl 0625.13003
[6] Bayer, D.; Morrison, I., Standard bases and geometric invariant theory, J. Symbolic Comput., 6, 209-217 (1988) · Zbl 0675.13014
[7] Berman, D., The number of generators of a colength \(N\) ideal in a power series ring, J. Algebra, 73, 156-166 (1981) · Zbl 0491.13013
[8] Billera, L.; Sturmfels, B., Fiber polytopes, Ann. Math., 135, 527-549 (1992) · Zbl 0762.52003
[9] Boshernitzan, M.; Fraenkel, A. S., Nonhomogeneous spectra of numbers, Discrete Math., 34, 325-327 (1981) · Zbl 0456.10005
[10] Boshernitzan, M.; Fraenkel, A. S., A linear algorithm for nonhomogeneous spectra of numbers, J. Algorithms, 5, 187-198 (1984) · Zbl 0555.65008
[12] Corteel, S.; Rémond, G.; Schaeffer, G.; Thomas, H., The number of plane corner cuts, Adv. Appl. Math., 23, 49-53 (1999) · Zbl 0955.52009
[13] Eisenbud, D., Commutative Algebra with a View toward Algebraic Geometry (1995), Springer-Verlag: Springer-Verlag New York · Zbl 0819.13001
[14] Gérard, Y., Analyse locale des droites discrètes. Généralisation et application à la connexité des plans discrets, C. R. Acad. Sci. Paris, Sér. I Math., 324, 1419-1424 (1997) · Zbl 0879.68086
[15] Hwang, F.; Onn, S.; Rothblum, U., Representations and characterizations of vertices of bounded-shape partition polytopes, Linear Algebra Appl., 278, 263-284 (1998) · Zbl 0947.90133
[17] Mora, T.; Robbiano, L., The Gröbner fan of an ideal, J. Symbolic Comput., 6, 183-208 (1988) · Zbl 0668.13017
[18] Schrijver, A., Theory of Linear and Integer Programming. Theory of Linear and Integer Programming, Series in Discrete Mathematics (1986), Wiley-Interscience: Wiley-Interscience Chichester · Zbl 0665.90063
[19] Stanley, R., Theory and applications of plane partitions, I, II, Stud. Appl. Math., 50, 167-188 (1971) · Zbl 0225.05011
[20] Sturmfels, B., Gröbner Bases and Convex Polytopes. Gröbner Bases and Convex Polytopes, University Lecture Notes, 8 (1995), American Mathematical Society: American Mathematical Society Providence
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.