# Delaunay Triangulation on Convex Polytopes — Uniform Sampling

My goal is to uniformly sample from a convex polytope. I know that for the simpler case, where I have to uniformly sample from a simplex, I can use Bayesian Bootstrap, discussed in these posts:

Uniform sampling from a simplex

Random vectors uniformely distributed into convex n-polytope

Therefore, I'm very interested in this approach. But I don't really know how to use Delaunay Triangulation here. What I have is a linear equation Ax = b and a non-negativity constraint that $x \geq \vec{0}$, and I want to sample x uniformly. Can someone tell me how to do the Delaunay Triangulation here? Thanks in advance!

• Is your simplex closed? Do you know rejection sampling; why is it not applicable here? – Raphael Jun 29 '15 at 14:33
• @Raphael Yes, the simplex is closed. I know rejection sampling, but it is very inefficient -- My sampling space has dimension 1000, so rejection sampling will filter out most of the points I sampled. – Miller Zhu Jun 30 '15 at 2:13

1. Bypassing KLS: Gaussian Cooling and an $O^*(n^3)$ Volume Algorithm by B. Cousins and S. Vempala (2014, preprint)