Subscribe
Subscribe
MY AMERICAN SCIENTIST
LOG IN! REGISTER!
SEARCH
 
Logo IMG

COMPUTING SCIENCE

An Adventure in the Nth Dimension

On the mystery of a ball that fills a box, but vanishes in the vastness of higher dimensions

Brian Hayes

Lost in Space

2011-11HayesFA.jpgClick to Enlarge ImageIn those childhood years when I was memorizing volume formulas, I also played a lot of ball games. Often the game was delayed when we lost the ball in the weeds beyond right field. I didn't know it then, but we were lucky we played on a two-dimensional field. If we had lost our ball in a space of many dimensions, we might still be looking for it.

The mathematician Richard Bellman labeled this effect “the curse of dimensionality.” As the number of spatial dimensions goes up, finding things or measuring their size and shape gets harder. This is a matter of practical consequence, because many computational tasks are carried out in a high-dimensional setting. Typically each variable in a problem description is mapped to a separate dimension.

A few months ago I was preparing an illustration of Bellman’s curse for an earlier Computing Science column. My first thought was to show the ball-in-a-box phenomenon. Put an n-dimensional ball in an n-dimensional cube just large enough to receive it. As n increases, the fraction of the cube’s volume occupied by the ball falls dramatically.

In the end I chose a different and simpler scheme for the illustration. But after the column appeared (“Quasirandom Ramblings,” July–August), I returned to the ball-in-a-box question out of curiosity. I had long thought that I understood it, but I realized that I had almost no quantitative data on the relative size of the ball and the cube.

(In this context “ball” is not just a plaything but also the mathematical term for a solid spherical object. “Sphere” itself is generally reserved for a hollow shell, like a soap bubble. More formally, a sphere is the locus of all points whose distance from the center is equal to the radius r. A ball is the locus of points whose distance from the center is less than or equal to r. And while I’m trudging through this mire of terminology, I should mention that “n-ball” and “n-cube” refer to an n-dimensional object inhabiting n-dimensional space. This may seem too obvious to bother stating, but some branches of mathematics adopt a different convention. In topology, a 2-sphere lives in 3-space.)




comments powered by Disqus
 

EMAIL TO A FRIEND :

Of Possible Interest

Spotlight: Briefings

Computing Science: Belles lettres Meets Big Data

Technologue: Quantum Randomness

Subscribe to American Scientist