03 August 2007

information theory for architects

Paul Bourke asks a question about the intersection of three cylinders (via Anarchaia):
Question. Is a 3D object uniquely described by a plan, front and side view?
Answer: No!
In particular, consider a sphere at the center of a Cartesian coordinate system. It can be inscribed in a cylinder with central axis the x-axis, or the y-axis, or the z-axis. The intersection of these three cylinders has the same plan, front, and side view (i. e. projections onto the three coordinate planes) as the sphere, but it's not a sphere. If you want to see what it looks like, there's a picture at the post, of one made from wood. Bourke writes:
I originally designed this object because Architecture students would ask me why the computer couldn't scan their plans and elevations and automatically build a 3D model. This was the simplest demonstration I could come up that there isn't enough information about a 3D object in its plane projections.
Thinking about how much "information" is contained in something is in general a useful idea. My first instinct is that these three projections, being plane curves, contain together about as much information as, say, three cross-sections of the object; you would never expect to be able to recreate an object from three of its cross-sections. I'm not sure if I would have been able to come up with this particular counterexample, but the previous argument would have reassured me that one probably exists.

But this sort of intuition can be misleading, especially when one is doing continuous (as opposed to discrete) mathematics. This line of reasoning would also lead you to think that Fourier series don't exist, because how can we encode uncountably many real numbers (the values of a function at every point in some real number) by only countably many real numbers (its Fourier coefficients)? The correct way to interpret this might be that functions which have Fourier series are somehow extremely rare among all functions, which is true because they've got to be piecewise smooth and continuous. I once asked a foolish question along these lines at a colloquium on the famous problem "Can you hear the shape of a drum?" The problem is basically what it sounds like. There's a membrane stretched in a certain shape, and when you hit it its motion is governed by a certain partial differential equation. The eigenvalues of the PDE, with boundary conditions governed by the shape of the drum are given to you; these correspond to the various frequencies one would hear in the sound if the drum were hit, hence the question. Can you (armed with an oscilloscope and a big fancy computer) tell what the drum looks like, if you don't get to see it? (The answer is "sort of".) It seemed to me for a moment that there's no way you could recover the whole shape from a countable sequence of numbers... but then I was reminded that Fourier series exist.

I prefer to only use this sort of intuition in discrete mathematics, because then usually one can count the things in question (at least in principle) since there are only finitely many of them. For example: it's easy to prove that any algorithm for sorting n items, where we're only allowed to compare them pairwise, must have runtime at least O(n log n). Basically, we want to determine which permutation of Sn is associated with the original list (in layman's terms, what order they started out in). From an information-theoretic point of view, each comparison gives us one bit of information; the total amount of information in the original permutation is log(n!), which is O(n log n) by Stirling's approximation.

1 comment:

John Armstrong said...

At Yale we used that shape as a standard homework for calculating surface areas and volumes in multivariable calculus classes.

Anyhow, it's a shame that the architects don't build harmonic buildings. Then they'd just have to scan the edges and convolve with the Poisson kernel to fill in the rest.