# Efficient algorithm for computing equally distributed points in polytope?

Given a $d$-dimensional (rational) convex polytope $P$ with vertices $v_1, \ldots, v_n$, I would like to compute many equally distributed points that lie in $P$. "Equally distributed" is of course not a precise term. It should just mean that points don't accumulate at some point in $P$ much more than at others (like they would be by doing a repeated barycentric subdivision, for example).

Now, there are two obvious solutions: First one is to just generate a lot of random points in the polytope. This can be done quickly with a software like Polymake. But the problem is that the coordinates have huge denominators which make subsequent computations very slow.

The second approach would be to generate coefficient vectors that sum up to $1$ and have entries $\geq 1/k$. The coefficients have small denominators but the algorithm would generate ${n-k-1 \choose k-1}$ coefficient vectors, while only a tiny fraction of them give distinct points in the polytope (at least for the polytopes I am interested in).

Are there any algorithms that do what I want efficiently with small denominators?

• can't you use the first solution and round the coordinates to integer multiples of $1/k$? it should not change uniformity all that much for a large enough $P$ – Sasho Nikolov Nov 20 '13 at 14:47
• One modification might be to "round the polytope" using a linear transformation before sampling and rounding the points (and then you transform it back). – Suresh Venkat Nov 20 '13 at 19:40