<p>This is an answer just to record a solution to the problem.</p>

<p>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.</p>

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

CC BY-SA 3.0
2013-11-25T15:07:20.413Z
2013-11-25T15:30:09.857Z
2013-11-25T15:30:09.857Z
Gregor
<p>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).</p>

<p>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.</p>

<p>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).</p>

<blockquote>
  <p>Are there any algorithms that do what I want efficiently with small denominators?</p>
</blockquote>

CC BY-SA 3.0
2013-11-20T14:47:39.223Z
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
CC BY-SA 3.0
2013-11-20T19:40:21.923Z
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
<ds.algorithms><cg.comp-geom><convex-geometry>
Efficient algorithm for computing equally distributed points in polytope?
Gregor
# Efficient algorithm for computing equally distributed points in polytope?

(Asked by: username_0 on 2013-11-20)

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?

**Tags:** ds.algorithms, cg.comp-geom, convex-geometry

> **Comments:**
> **username_1**: 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$  
> **username_2**: One modification might be to "round the polytope" using a linear transformation before sampling and rounding the points (and then you transform it back).  

---

## 1 answers

### Answer by username_0 on 2013-11-25. Score: 2

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.


---

