Stochastic Billiards for Sampling from the Boundary of a Convex Set

References

• Applegate D, Kannan R (1991) Sampling and integration of near log-concave functions. STOC '91: Proc. Twenty-Third Annual ACM Sympos. Theory Comput. (ACM, New York), 156–163.Crossref, Google Scholar
• Bárány I, Füredi Z (1987) Computing the volume is difficult. Discrete Comput. Geom. 2:319–326.Crossref, Google Scholar
• Belkin M, Narayanan H, Niyogi P (2013) Heat flow and a faster algorithm to compute the surface area of a convex body. Random Structures Algorithms 43(4):407–428.Crossref, Google Scholar
• Boender CGE, Caron RJ, Rinnooy Kan AHG, Romeijn HE, Smith RL, Telgen J, Vorst ACF (1991) Shake-and-bake algorithms for generating uniform points on the boundary of bounded polyhedra. Oper. Res. 39(6):945–954.Link, Google Scholar
• Boneh A, Golan A (1979) Constraints' redundancy and feasible region boundedness by random feasible point generator (RFPG). Third Eur. Congress Oper. Res. (EURO III), Amsterdam.Google Scholar
• Comets F, Popov S, Schütz GM, Vachkovskaia M (2009) Billiards in a general domain with random reflections. Arch. Ration. Mech. Anal. 191:497–537.Crossref, Google Scholar
• Cousins B, Vempala S (2013) A cubic algorithm for computing Gaussian volumes. Proc. 25th Annual ACM-SIAM Sympos. Discrete Algorithms, SODA '14 (SIAM, Philadelphia), 1215–1228.Crossref, Google Scholar
• Diaconis P, Holmes S, Shahshahani M (2013) Sampling from a manifold. Collections, Vol. 10 (Institute of Mathematical Statistics, Beachwood, OH), 102–125.Crossref, Google Scholar
• Dieker AB, Kim S-H (2014) A high-dimensional ellipsoid-based method for ranking and selection. Preprint.Google Scholar
• Dyer M, Gritzmann P, Hufnagel A (1998) On the complexity of computing mixed volumes. SIAM J. Comput. 27:356–400.Crossref, Google Scholar
• Dyer ME, Frieze AM, Kannan R (1989) A random polynomial time algorithm for approximating the volume of convex bodies. Proc. 21st ACM Sympos. Theory Comput. STOC '89 (ACM, New York), 375–381.Crossref, Google Scholar
• Evans SN (2001) Stochastic billiards on general tables. Ann. Appl. Probab. 11(2):419–437.Crossref, Google Scholar
• Lalley S, Robbins H (1988) Stochastic search in a convex region. Probab. Theory Related Fields 77(1):99–116.Crossref, Google Scholar
• Lovász L (1998) Hit-and-run mixes fast. Math. Prog 86:443–461.Google Scholar
• Lovász L, Simonovits M (1993) Random walks in a convex body and an improved volume algorithm. Random Structures Algorithms 4:359–412.Crossref, Google Scholar
• Lovász L, Vempala S (2006) Fast algorithms for logconcave functions: Sampling, rounding, integration and optimization. Proc. 47th Annual IEEE Sympos. Foundations Comput. Sci. FOCS '06 (IEEE Computer Society, Washington, DC), 57–68.Crossref, Google Scholar
• Lovász L, Vempala S (2006) Hit-and-run from a corner. SIAM J. Comput. 35:985–1005.Crossref, Google Scholar
• Lovász L, Vempala S (2006) Simulated annealing in convex bodies and an O*(n4) volume algorithm. J. Comput. Syst. Sci. 72(2): 392–417.Crossref, Google Scholar
• Milman E (2011) Isoperimetric bounds on convex manifolds. Houdré C, Ledoux M, Milman E, Milman M, eds. Concentration, Functional Inequalities and Isoperimetry, Contemporary Mathematics, Vol. 545 (AMS, Providence, RI), 195–208.Crossref, Google Scholar
• Narayanan H, Niyogi P (2008) Sampling hypersurfaces through diffusion. Approximation, Randomization and Combinatorial Optimization, Lecture Notes in Computer Science, Vol. 5171 (Springer, Berlin), 535–548.Crossref, Google Scholar
• Romeijn HE (1991) Shake-and-bake algorithms for the identification of nonredundant linear inequalities. Statist. Neerlandica 45:31–50.Crossref, Google Scholar
• Romeijn HE (1998) A general framework for approximate sampling with an application to generating points on the boundary of bounded convex regions. Statist. Neerlandica 52:42–59.Crossref, Google Scholar
• Smith RL (1984) Efficient Monte Carlo procedures for generating points uniformly distributed over bounded regions. Oper. Res. 32:1296–1308.Link, Google Scholar
• Vempala S (2005) Geometric random walks: A survey. MSRI Combin. Computational Geometry 52:573–612.Google Scholar
• Yau ST (1975) Isoperimetric constants and the first eigenvalue of a compact Riemannian manifold. Ann. Sci. École Norm. 8(4):487–507.Google Scholar