2 fixed LaTeX

Let $n \in \mathbf{Z}_{\geq 1}$. Is there an algorithm which, given a simplex $\Delta \subset \mathbf{R}^n$ specified as the convex hull of $v_0,\dots,v_n \in \mathbf{Z}^n$, computes the set $\Delta \cap \mathbf{Z}^n$ in time $O(\delta^t\mathrm{vol}(\Delta))$ for some explicit $t \in \mathbf{R}$, where $\delta=\max_{i,j} \log|v_{ij}|$ is the input size and $\mathrm{vol}(\Delta)$ is the (normalized) volume of $\Delta$?

Note here that the dimension is fixed. Implicit in this question is that $|\Delta \cap \mathbf{Z}^n|=O(\mathrm{vol}(\Delta))$, which I haven't been able to extract yet from the literature.

This question arises for me after trying to ask the same thing for a polytope $P \subset \mathbf{Z}^n$; the natural way to do this seems to be by computing a triangulation (or do people say tetrahedralization?), such as the Delaunay triangulation, which reduces the problem from $P$ to a bunch of $\Delta$s.

(And in fact, really what I need is to compute $d\Delta \cap \mathbf{Z}^n$ for $d=O(n)$, but $n$ is constant for now so this doesn't seem to help.)

People often just want to count the set $\Delta \cap \mathbf{Z}^n$ (use short rational generating functions) or to know that it is nonempty (reduces to an integer program), but I need to actually list every lattice point.

Translating by $v_0$ we may assume $v_0=0$ is a vertex, and then we want to compute the set of points $x=a_1v_1+\dots+a_n v_n$ such that $a_i \geq 0$ for all $i$ and $a_1+\dots+a_n \leq 1$. This should be doable by considering representatives for $\Z^n/\sum Z \mathbf{Z}^n/\sum \mathbf{Z} v_i$ via a Hermite normal form, but this gives generators for the whole parallelopiped (wasteful, but perhaps not noticeably so in fixed dimension)? If this makes sense, is there a clean algorithm with a rigorous analysis of the running time (counting the time for integer arithmetic)?

Thanks very much for your help!

1

# Listing lattice points in a simplex

Let $n \in \mathbf{Z}_{\geq 1}$. Is there an algorithm which, given a simplex $\Delta \subset \mathbf{R}^n$ specified as the convex hull of $v_0,\dots,v_n \in \mathbf{Z}^n$, computes the set $\Delta \cap \mathbf{Z}^n$ in time $O(\delta^t\mathrm{vol}(\Delta))$ for some explicit $t \in \mathbf{R}$, where $\delta=\max_{i,j} \log|v_{ij}|$ is the input size and $\mathrm{vol}(\Delta)$ is the (normalized) volume of $\Delta$?

Note here that the dimension is fixed. Implicit in this question is that $|\Delta \cap \mathbf{Z}^n|=O(\mathrm{vol}(\Delta))$, which I haven't been able to extract yet from the literature.

This question arises for me after trying to ask the same thing for a polytope $P \subset \mathbf{Z}^n$; the natural way to do this seems to be by computing a triangulation (or do people say tetrahedralization?), such as the Delaunay triangulation, which reduces the problem from $P$ to a bunch of $\Delta$s.

(And in fact, really what I need is to compute $d\Delta \cap \mathbf{Z}^n$ for $d=O(n)$, but $n$ is constant for now so this doesn't seem to help.)

People often just want to count the set $\Delta \cap \mathbf{Z}^n$ (use short rational generating functions) or to know that it is nonempty (reduces to an integer program), but I need to actually list every lattice point.

Translating by $v_0$ we may assume $v_0=0$ is a vertex, and then we want to compute the set of points $x=a_1v_1+\dots+a_n v_n$ such that $a_i \geq 0$ for all $i$ and $a_1+\dots+a_n \leq 1$. This should be doable by considering representatives for $\Z^n/\sum Z v_i$ via a Hermite normal form, but this gives generators for the whole parallelopiped (wasteful, but perhaps not noticeably so in fixed dimension)? If this makes sense, is there a clean algorithm with a rigorous analysis of the running time (counting the time for integer arithmetic)?

Thanks very much for your help!