The Accessibility of Convex Bodies and Derandomization of the Hit and Run Algorithm
Journal of convex analysis, Tome 24 (2017) no. 3, pp. 903-916
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.
@article{JCA_2017_24_3_JCA_2017_24_3_a8,
author = {B. Collins and T. Kousha and R. Kulik and T. Szarek and K. Zyczkowski},
title = {The {Accessibility} of {Convex} {Bodies} and {Derandomization} of the {Hit} and {Run} {Algorithm}},
journal = {Journal of convex analysis},
pages = {903--916},
year = {2017},
volume = {24},
number = {3},
url = {http://geodesic.mathdoc.fr/item/JCA_2017_24_3_JCA_2017_24_3_a8/}
}
TY - JOUR AU - B. Collins AU - T. Kousha AU - R. Kulik AU - T. Szarek AU - K. Zyczkowski TI - The Accessibility of Convex Bodies and Derandomization of the Hit and Run Algorithm JO - Journal of convex analysis PY - 2017 SP - 903 EP - 916 VL - 24 IS - 3 UR - http://geodesic.mathdoc.fr/item/JCA_2017_24_3_JCA_2017_24_3_a8/ ID - JCA_2017_24_3_JCA_2017_24_3_a8 ER -
%0 Journal Article %A B. Collins %A T. Kousha %A R. Kulik %A T. Szarek %A K. Zyczkowski %T The Accessibility of Convex Bodies and Derandomization of the Hit and Run Algorithm %J Journal of convex analysis %D 2017 %P 903-916 %V 24 %N 3 %U http://geodesic.mathdoc.fr/item/JCA_2017_24_3_JCA_2017_24_3_a8/ %F JCA_2017_24_3_JCA_2017_24_3_a8
B. Collins; T. Kousha; R. Kulik; T. Szarek; K. Zyczkowski. The Accessibility of Convex Bodies and Derandomization of the Hit and Run Algorithm. Journal of convex analysis, Tome 24 (2017) no. 3, pp. 903-916. http://geodesic.mathdoc.fr/item/JCA_2017_24_3_JCA_2017_24_3_a8/