Journal of Convex Analysis 24 (2017), No. 3, 903--916
Copyright Heldermann Verlag 2017
The Accessibility of Convex Bodies and Derandomization of the Hit and Run Algorithm
Benoît Collins
Dép. de Mathématique et Statistique, Université d'Ottawa, 585 King Edward, Ottawa, Ontario, Canada K1N6N5
bcollins@uottawa.ca
Termeh Kousha
Dép. de Mathématique et Statistique, Université d'Ottawa, 585 King Edward, Ottawa, Ontario, Canada K1N6N5
tkousha@uottawa.ca
Rafal Kulik
Dép. de Mathématique et Statistique, Université d'Ottawa, 585 King Edward, Ottawa, Ontario, Canada K1N6N5
rkulik@uottawa.ca
Tomasz Szarek
Dept. of Mathematics, University of Gdansk, ul. Wita Stwosza 57, 80-952 Gdansk, Poland
szarek@intertele.pl
Karol Zyczkowski
Institute of Physics, Jagiellonian University, ul. Reymonta 4, 30-059 Kraków, Poland
karol@tatry.if.uj.edu.pl
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.
[ Fulltext-pdf (161 KB)] for subscribers only.