The accessibility of convex bodies and derandomization of the hit and run algorithm

Abstract

We introduce the concept of accessibility and prove that any convex body $X$ in ${\mathbb{R}}^d$ is accessible with relevant constants depending on $d$ only. This property leads to a new algorithm which may be considered as a natural derandomization of the hit and run algorithm applied to generate a sequence of random points covering $X$ uniformly. We prove stability of the Markov chain generated by the proposed algorithm and provide its rate of convergence.

arXiv commentrevised version, new title and abstract; 13 pages, 2 figures