Re:What algorithm blows your mind? (Reddit compsci)
by jules on Tuesday October 26, 2010 @11:15AM
(#1834508)
Why are high dimensional spheres spikey?
Re:What algorithm blows your mind? (Reddit compsci)
by RiderOfGiraffes on Tuesday October 26, 2010 @11:56AM
(#1834678)
Ah. I really should write that up. Far too long to explain in a comment here, far to interesting (to me!) to forget or ignore.
I'll write it up and submit it. Anyone who cares to email me can get an early version to read, and your feedback would be useful.
Please.
Thanks.
Re:What algorithm blows your mind? (Reddit compsci)
by orangecat on Tuesday October 26, 2010 @02:01PM
(#1835294)
Please do. My guess would be similar to Zaak's: the n-dimensional volume of an n-dimensional hypersphere approaches 0 as n approaches infinity. (http://www.mathreference.com/ca-int,hsp.html). A hypersphere with radius 1 centered at the origin has to get out to 1 along each axis (e.g. x=1, y=z=0 for a 3 dimensional sphere), and in order for that not to contribute much volume, it has to be a narrow spike rather than a gradual curve.
Re:What algorithm blows your mind? (Reddit compsci)
by RiderOfGiraffes on Friday October 29, 2010 @09:36AM
(#1847242)
In response to requests, the write-up is now available here:
Re:What algorithm blows your mind? (Reddit compsci)
by Zaak on Tuesday October 26, 2010 @01:14PM
(#1835058)
I believe it's because in high dimensions, most of the "volume" is near the center, whereas in low dimensions, most of the volume is near the surface.
Re:What algorithm blows your mind? (Reddit compsci)
by cperciva on Tuesday October 26, 2010 @01:34PM
(#1835159)
Not at all. The expected distance between the center of an n-ball and a random point in the ball is n/(n+1) times the radius.
Now, if you look at an n-sphere with respect to orthogonal axes, you find that moving along an axis you get out as far as (1, 0, ... 0) and moving "away" from the axes you only get to (1/sqrt(n), 1/sqrt(n), ... 1/sqrt(n)); but this isn't due to the sphere being spiky -- rather, it's because orthogonal axes are spiky.
Re:What algorithm blows your mind? (Reddit compsci)
by RiderOfGiraffes on Friday October 29, 2010 @09:18AM
(#1847180)
Now written up here:
http://en.wikipedia.org/wiki/Lenstra%E2%80%93Lenstra%E2%80%9...
High dimensional work is bloody hard, and this algorithm works amazingly well. I've spoken with Lenstra (one of them) and he's amazingly insightful on these things. He helped to crystalise my understanding of why high-dimensional spheres should be thought of as "spikey," rather than "round."