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
  • 1
    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

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

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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