Clearer porcupine math in Chapter 2 #209

Open
searchivarius opened this Issue Sep 15, 2016 · 2 comments

Projects

None yet

1 participant

@searchivarius
searchivarius commented Sep 15, 2016 edited

Hi! I just started reading the book to referesh some of my memories. I really like the pedagogical approach.

However, your porcupine example doesn't fully make sense to me. For one thing, I don't understand how one can formally extend your math to d-dimensions. For another thing, high dimensional balls are perfectly round. So the porcupine analogy seems to be flaky. If you believe that there's indeed a porcupine happening, you should be able to find a projection that preservers this porcupine. However, projection of a convex body is still convex. The porcupine is not.

So, my first suggestion is to make the math more clear. Simply speaking, it seems to be quite non-trivial to see how you apply the Pythagorean theoream in d-dimensional space.

I originally did calculations with the picture that is correct only in 2-d. In another comment I attach a picture that makes more sense in high dimensions. My understanding is that the middle sphere can touch other spheres only along one of the "main" diagonals that all have lengths 2 sqrt(d). The length of the main diagonal is obviously the Euclidean distance between d-dimensional points (0,0,....,0) and (2,2,...,2).

The mere fact that diagonal length is growing unboundly is already an anomaly, which explains a lot of things. Furthremore, the total volume of spheres other than the central one becomes inifintely small compared to the volume of the cube. There is a lot of empty space, where you can fit the middle sphere. BTW, the empty space phenomenon is another problem in high dimensions.

So, let's get back to math. To compute the diamter of the central (black) circle you should simply subtract twice the diameter of the two spheres and twice the length of EB (see the picture). To compute the length of EB, you need to compute OB. However, it is a "main diagonal" of the smaller cube that has side 1. Hence, the length of OB is sqrt(d). The rest of the math is shown in the picture.

Please, also see an additional comment to this issue.

porcupine math

@searchivarius
searchivarius commented Sep 15, 2016 edited

So, in this comment, I just draw a better projection picture that is valid for d > 2. Dashes indicate invisible lines. So, you can see the diagonal AB is visible, then it is covered by the sphere (dashed line), then it is kinda visible in the center.

The boundary of the central sphere is also dashed when it's covered by other spheres. You can also easily find the projections of points where the central sphere touches other spheres.

As dimensionality grows, the cosine of the angle between AB and any adjacent cube edge converges to zero and the diagonal approaches a perpindicular to the projection surface (follows from calculating the scalar product between (1,0,0, ....,0) and (1,1,1...,1)). Again, another high-dimensional anomaly! Consequently, the projection of the point where the middle sphere touches the left upper sphere approaches point A (in the projection).

This again, makes a lot of sense, because the diameter of the central sphere (2sqrt(d)-2) converges to the length of the diagonal (2sqrt(d)). So, as dimensionality grows the central sphere grows in diameter and eventually starts to stick out of the cube. In that, the central ball remains perfectly round and only touches other spheres.

To sum up, the ball is not a porcupine. The fact that the ball can stick out while touching the spheres is not a roundness anomaly it is a packing anomaly apparently due to the emptyness of the space. Or so it seems. Does it make sense?

BTW, you can do math using this (apparently more appropriate picture) fully formally. But I was just lazy to redraw everything. Again, this is based on my understanding that spheres touch along diagonals. This seems to be correct on a first thought, but I didn't verify it very carefully.

porcupine math better picture

@searchivarius
searchivarius commented Sep 15, 2016 edited

PS: another suggestion. If you talk about anomalies, it may be worth mentioning that nearly all the volume of the sphere is concentrated in a shell near surface. This seems to have a lot of implications.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment