Curse of Dimensionality ... as illustrated by Christopher Bishop I'm reading Christopher Bishop's book "Neural Networks for Pattern Recognition". I'm on pg 7 about curse of dimensionality. 
Here is the relevant part: 
For simplicity assume the dimensionality we are working with is 3. Now "divide the input variables $x_1, \dots x_d$ into M intervals, so that the value of a variable can be specified approximately by saying in which interval it lies. This leads to a division of the whole input space into a large number of [3D] boxes or cells ...
Each of the training examples corresponds to a point in one of the cells , and carries an associated value of the output variable $y$. ... [To find $y$ for a given point], by finding which cell the point falls in, and then returning the average value of y for all training points that lie in that cell."
The claim is that if each input variable is divided into $M$ divisions, then the total number of cells is $M^d$.
First and foremost, why is this true? Why do we need $M^d$ cells? Secondly, what does it mean to divide an input variable into intervals or divisions. (I assume an input variable is $x_i$ from $x_1, \dots, x_d$ for $1\leq i \leq d$.)
I'm interested in making sure that I understand this because this seems (at least to me) a clever way of thinking about the curse of dimensionality.

Let's be explicit and consider $M=3$.  If $d=1$, then you divide a segment into three subsegments. For example you divide the interval $[0,1]$ into $[0,1/3)$, $(1/3,2/3]$, and $(2/3,1]$.
If $d=2$, then you divide a square into thirds horizontally and also vertically, so there are $9$ areas.  If $d=3$, then you divide a cube into thirds in all three directions, like a Rubik's cube, leading to $3^3=27$ volumes.  That's why you need $M^d$ cells.
