Enumerating projections of integer points in unbounded polyhedra

2016/12/23 by Danny Nguyen, Nguyen, Danny, Igor Pak +1
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Advanced Graph Theory Research #Combinatorics (math.CO) #Commutative Algebra and Its Applications #Computational Geometry (cs.CG) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Logic (math.LO) #Logic in Computer Science (cs.LO)

paper · pdf · doi:10.48550/arxiv.1612.08030

openalex publication_date 2016/12/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We extend the Barvinok-Woods algorithm for enumerating projections of integer points in polytopes to unbounded polyhedra. For this, we obtain a new structural result on projections of semilinear subsets of the integer lattice. We extend the results to general formulas in Presburger Arithmetic. We also give an application to the k-Frobenius problem.

Related

• Lattice point enumeration of polytopes associated to integer compositions
• Enumerating integer points in polytopes with bounded subdeterminants
• Short rational generating functions for lattice point problems
• Computing convex hulls and counting integer points with polymake
• An Efficient Algorithm for Vertex Enumeration of Two-Dimensional Projection of Polytopes