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?

  • $\begingroup$ 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$ $\endgroup$ Nov 20, 2013 at 14:47
  • 1
    $\begingroup$ One modification might be to "round the polytope" using a linear transformation before sampling and rounding the points (and then you transform it back). $\endgroup$ Nov 20, 2013 at 19:40

1 Answer 1


This is an answer just to record a solution to the problem.

Given the polytope, I triangulate it without introducing new vertices. Then I generate for each simplex in the resulting simplicial complex many points in the interior with my second approach. Every coefficient vector will give distinct points because the vertices of the simplices are affinely independent. To implement this solution one can use Sage together with TOPCOM, for example.

Depending on the chosen triangulation, the dimension and and number of vertices this solution can actually be quite inefficient.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.