Premium
Volumes Spanned by Random Points in the Hypercube
Author(s) -
Dyer M. E.,
Füredi Z.,
McDiarmid C.
Publication year - 1992
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.3240030107
Subject(s) - hypercube , combinatorics , mathematics , volume (thermodynamics) , convex hull , constant (computer programming) , regular polygon , discrete mathematics , physics , geometry , computer science , quantum mechanics , programming language
Consider the hypercube [0, 1] n in R n . This has 2 n vertices and volume 1. Pick N = N(n) vertices independently at random, form their convex hull, and let V n be its expected volume. How large should N(n) be to pick up significant volume? Let k =2/√≈1.213, and let ϵ > 0. We shall show that, as n→∞, V n →0 if N(n)⩽(k−ϵ) n →1 if N(n) ⩾ ( k + ϵ) n . A similar result holds for sampling uniformly from within the hypercube, with constant .