An Algorithmic Theory of Lattice Points in Polyhedra
An Algorithmic Theory of Lattice Points in Polyhedra
复制标题
多面体格点的算法理论
DOI：
--
复制
发表时间：
1999
期刊：
影响因子：
--
通讯作者：
James Pommersheim
中科院分区：
文献类型：
--
作者：
A. Barvinok;James Pommersheim
我们讨论了与有理多面体中的格点相关的主题，包括格点的有效枚举，有理多面体中格点的“短”生成函数，与经典和高维Dedekind和的关系，Presburger算法的复杂性，有理函数的有效计算等。虽然主要的倾斜是算法，结构的结果进行了讨论，如关系到一般理论的估值多面体和连接与理论的复曲面品种。本文综述了已有的结果，并提出了一些新的结果和联系。
We discuss topics related to lattice points in rational polyhedra, including efficient enumeration of lattice points, “short” generating functions for lattice points in rational polyhedra, relations to classical and higher-dimensional Dedekind sums, complexity of the Presburger arithmetic, efficient computations with rational functions, and others. Although the main slant is algorithmic, structural results are discussed, such as relations to the general theory of valuations on polyhedra and connections with the theory of toric varieties. The paper surveys known results and presents some new results and connections.