The Accessibility of Convex Bodies and Derandomization of the Hit and Run Algorithm

We introduce the concept of accessibility and prove that any convex body X in the d-dimensional Euclidean space 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