November 29, 2010

What is Integral Geometry?

Posted by Tom Leinster

Spurred by an interest in metric spaces, I also got interested in integral geometry. But until quite recently I had no idea what it was. I’m guessing some of you have no idea either. The aim of this post is to give you a fast, very concrete explanation.

Here are three problems.

1. Let $X$ be a cube in $\mathbb{R}^3$. What is the expected area of the orthogonal projection of $X$ onto a random plane through the origin?
2. Let $X$ be a cube in $\mathbb{R}^3$, and suppose that $X$ sits inside some bigger cube $\hat{X}$. What is the probability that a random straight line in $\mathbb{R}^3$ (not necessarily through the origin) meets $X$, given that it meets $\hat{X}$?
3. Let $X$ be a cube in $\mathbb{R}^3$, again sitting inside a bigger cube $\hat{X}$. Place a ball $Y$ of unit radius somewhere at random in $\mathbb{R}^3$, choosing uniformly among all positions such that $Y$ meets $\hat{X}$. What is the probability that $Y$ meets $X$?

You could probably figure out answers by a direct attack involving lots of integration. Things would get pretty ugly.

But integral geometry provides shockingly easy answers to all three questions—without doing any integrals!

Of course, it’s not just about these specific questions. For a start, the cubes $X$ and $\hat{X}$ and the ball $Y$ could be replaced by any compact convex sets, and the answers would still be easy. The space $\mathbb{R}^3$ could be replaced by any $\mathbb{R}^n$, and the lines and planes could be replaced by subspaces of any dimension. And there are other questions you can ask, though these are quite typical.

The formulas supplying the answers to the questions are called, respectively, Cauchy’s formula (or the mean projection formula), Crofton’s formula, and the kinematic formula. In fact, questions 1 and 2 are so closely related that there’s some blurring of the names; can you see why?

What makes these questions so shockingly easy to answer—once you know how—is the existence of some invariants called intrinsic volumes. I’ll explain it just for convex subsets of $\mathbb{R}^3$. Exact answers to all three questions can be given if you just have the following information about each of the spaces $X$, $\hat{X}$ and $Y$:

• the volume
• the surface area
• the mean width
• whether it’s empty.

(The mean width of a convex subset of $\mathbb{R}^3$ is its expected width, say in the direction of the $x$-axis, when it is oriented randomly. For example, the mean width of a ball is its diameter.) The formulas I named give answers to the questions in terms of these four invariants alone.

For example, the answer to the first question is ‘one quarter of the surface area of $X$’. We used this over at Azimuth to help with a problem about solar radiation.

Posted at November 29, 2010 5:32 AM UTC

TrackBack URL for this Entry:   http://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/2312

Re: What is Integral Geometry?

One of my favorite applications of integral geometry-type invariants is MacPherson and Srolovitz’s generalization of von Neumann’s law for grain growth to higher dimensions.

Roughly, one should think of a foam or the pattern of grains in a metal or other crystalline material (there’s a difference between foams and grains, but this is unimportant for the current purposes). The boundaries between the grains or the films in the foam evolve in time with normal speed proportional to the local curvature, see e.g. this experimental movie or this simulation.

von Neumann showed for 2D grains using a simple Gauss-Bonnet type argument that the rate of area change of each cell depends only on the number of sides minus 6; i.e. the rate of grain growth is topological!

Much effort went into trying to find an appropriate generalization, until MacPherson and Srolovitz showed that the proper generalization in 3D was that the rate of volume change was proportional to a quantity related to the mean width, and in higher dimensions, other integral geometric invariants! Check out the paper and supplementary information if you’re interested. It’s very readable.

Posted by: j.c. on November 29, 2010 4:32 PM | Permalink | Reply to this

Re: What is Integral Geometry?

Thanks! A colleague who does the mathematics of materials told me about MacPherson and Srolovitz’s paper a little while back. I was tickled to be able to cite it in a paper on category theory. It’s a spectacular application of the intrinsic volumes.

I’ll re-post their abstract here (with some paragraph breaks inserted). The full paper is behind a paywall (Nature 446 (2007), 1053–1055).

Cellular structures or tessellations are ubiquitous in nature. Metals and ceramics commonly consist of space-filling arrays of single-crystal grains separated by a network of grain boundaries, and foams (froths) are networks of gas-filled bubbles separated by liquid walls. Cellular structures also occur in biological tissue, and in magnetic, ferroelectric and complex fluid contexts.

In many situations, the cell/grain/bubble walls move under the influence of their surface tension (capillarity), with a velocity proportional to their mean curvature. As a result, the cells evolve and the structure coarsens.

Over 50 years ago, von Neumann derived an exact formula for the growth rate of a cell in a two-dimensional cellular structure (using the relation between wall velocity and mean curvature, the fact that three domain walls meet at 120° and basic topology). This forms the basis of modern grain growth theory.

Here we present an exact and much-sought extension of this result into three (and higher) dimensions. The present results may lead to the development of predictive models for capillarity-driven microstructure evolution in a wide range of industrial and commercial processing scenarios—such as the heat treatment of metals, or even controlling the ‘head’ on a pint of beer.

Posted by: Tom Leinster on November 29, 2010 7:03 PM | Permalink | Reply to this

Re: What is Integral Geometry?

John just told me by email that he has no idea what a cuboid is. I suspect this is a British/American thing, as I’m sure that when I was at school, everyone was learning about cuboids by age 10 or so. In any case, on the assumption that John’s not alone, I followed his suggestion and changed all the occurrences of “cuboid” to “cube”.

For what it’s worth, a cuboid (in my usage) is something congruent to $[0, a] \times [0, b] \times [0, c] \subseteq \mathbb{R}^3$. (And like everyone else, I use “cube” to mean something congruent to $[0, a]^3$. So the new questions are a bit less general than the old.)

Posted by: Tom Leinster on November 29, 2010 7:47 PM | Permalink | Reply to this

Re: What is Integral Geometry?

For what it’s worth, a cuboid (in my usage) is something congruent to $[0,a]\times [0,b]\times [0,c]\subseteq \mathbb{R}^3$.

I would probably call that a “rectangular parallelpiped”, a “rectangular prism”, or a “box.” A “cube” to me would be something congruent to $[0,a]^3$. Do you call a rectangle a “squareoid”? (-:

Posted by: Mike Shulman on November 29, 2010 9:34 PM | Permalink | Reply to this

Re: What is Integral Geometry?

Ronnie Brown calls them hyperrectangles

Posted by: jim stasheff on November 30, 2010 1:23 PM | Permalink | Reply to this

Re: What is Integral Geometry?

Do you call a rectangle a “squareoid”? (-:

No, but I call a stretched-out version of a group a “groupoid”.

Posted by: Tom Leinster on November 29, 2010 10:03 PM | Permalink | Reply to this

Re: What is Integral Geometry?

To add plausibility to the British/American thing—I learned to use the term “cuboid” in primary school too. I don’t think I was even as old as ten; maybe seven or eight.

Posted by: Tim Silverman on November 30, 2010 2:15 PM | Permalink | Reply to this

Re: What is Integral Geometry?

If you’ve got time to waste and want to be amused by how mainstream the British importance of correct cube/cuboid terminology is, you can look at this youtube clip someone has recorded from a programme that is Saturday night mainstream TV.

Posted by: dave tweed on December 5, 2010 9:31 PM | Permalink | Reply to this

Re: What is Integral Geometry?

While of course I’m far too important to have time to waste, I did watch the youtube clip and was amused. Thanks! It’s hard to imagine making the point more vividly.

Posted by: Tom Leinster on December 15, 2010 6:02 PM | Permalink | Reply to this

Re: What is Integral Geometry?

To me, anything of the form $U \times V$ is a “rectangle”. Certainly in place of “cuboid” I would be perfectly happy with “rectangle” or “$n$-dimensional rectangle”.

Posted by: Theo on August 26, 2011 3:15 AM | Permalink | Reply to this

Re: What is Integral Geometry?

This is really beautiful, although I’m not sure I’ve properly understood the setup (rummaging around on Google for a bit turned up a lot of generalizations and relatively little in the way the basics.)

Suppose I take two blocks $X,Y$ of the same dimensions $[a,b,c]$ with $a,b,c \lt 1$, and specify that they are both confined to $\mathbb{I}^3$. If I prescribe their orientations ahead of time, but otherwise let them sit randomly within $\mathbb{I}^3$, does the kinematic theorem imply that the orientations I chose don’t affect the probability that $X$ and $Y$ intersect? Or does specifying the orientations ahead of time alter the underlying measure and cause the “mean width” of the sets $X,Y$ to change (and thus the outcome of the calculation)?

Concretely, if I have two bricks, and I stick one of them vertically on end, does that change the probability that they intersect versus having them both lying flat? Or do these results depend on the bricks being able to spin freely?

Posted by: Scott McKuen on November 30, 2010 3:01 AM | Permalink | Reply to this

Re: What is Integral Geometry?

Thanks for your comments. The results depend on the bricks being able to spin freely. That wasn’t apparent from what I wrote, since in my example it was a ball that was being placed at random—and for a ball, spinning it around makes no difference.

Maybe it would clarify things to put them more formally. First we need to formalize what “probability” means. Let $G$ be the group of Euclidean motions of $\mathbb{R}^3$, generated by translations and rotations. The Haar measure theorem tells us that there’s a measure on $G$, invariant under multiplication $g\cdot-$ by any $g \in G$, and that this measure is unique up to a scalar factor.

This allows us to talk about “random Euclidean motions”. For any $X, \hat{X}, Y \subseteq \mathbb{R}^3$, there’s a well-defined quantity $Prob(g Y  \text{ meets }  X | g Y  \text{ meets }  \hat{X}).$ Writing the measure as $\mu$, this is $\frac{\displaystyle\mu\{g \in G: g Y \cap X \neq \emptyset \}}{\displaystyle\mu\{g \in G: g Y \cap \hat{X} \neq \emptyset \}}.$ (The choice of normalization doesn’t affect this quantity.)

The kinematic formula tells us what this probability is when $X$, $\hat{X}$ and $Y$ are convex. Here it is. Write $V_0(X)$ for the Euler characteristic of $X$ (which is $0$ if $X$ is empty, and $1$ otherwise). Write $V_1(X)$ for its mean width, $V_2(X)$ for its surface area, and $V_3(X)$ for its volume. Then the probability is $\frac{\displaystyle c_0 V_0(X) V_3(Y) + c_1 V_1(X) V_2(Y) + c_2 V_2(X) V_1(Y) + c_3 V_3(X) V_0(Y)}{\displaystyle c_0 V_0(\hat{X}) V_3(Y) + c_1 V_1(\hat{X}) V_2(Y) + c_2 V_2(\hat{X}) V_1(Y) + c_3 V_3(\hat{X}) V_0(Y)}$ where $c_0$, $c_1$, $c_2$ and $c_3$ are constants whose values I could look up (or if I were feeling smart, work out). Though this formula is longish, it’s of a fairly primitive type.

(Professionals might frown and say that some of my definitions of the $V_i$s are out by a constant factor, but seeing as I haven’t specified what the $c_i$s are, it doesn’t matter.)

Incidentally, I’m not aware of places on the web where the basics of this kind of thing are covered. I learned them from a nice little book by Klain and Rota, which doubtless you’ll want to own yourself, but you can “preview” it here.

Posted by: Tom Leinster on November 30, 2010 3:36 AM | Permalink | Reply to this

Re: What is Integral Geometry?

PS: To answer your questions directly: (1) no, the kinematic theorem doesn’t imply any kind of orientation-independence; (2) yes, specifying the orientations ahead of time does alter the answer (and “mean width” is an intrinsic property of a convex body, not depending on a choice of orientation), (3) yes, choosing to place one brick vertically does change the probability, and (4) yes, the results depend on the bricks being able to spin freely.

If you go down a dimension and think about two straight line segments, things might become clearer. If they’re both constrained to lie horizontally then the probability that they’ll meet is zero. If one is constrained to lie horizontally and the other constrained to lie vertically then the probability is nonzero.

Posted by: Tom Leinster on November 30, 2010 6:42 AM | Permalink | Reply to this

Re: What is Integral Geometry?

It looks like integral geometry directly related to 3d reconstruction and computer vision generally. Fascinating! Havn’t seen many computer vision works on that subject. Only one I read that was remotely related was statistical analysis of projective invariants.

Posted by: mirror2image on November 30, 2010 9:41 AM | Permalink | Reply to this

Re: What is Integral Geometry?

That’s very plausible, though I don’t know anything about it. What I do know is that there’s a book called Geometric Tomography by Richard Gardner that’s used as a reference for pure integral geometry.

Tomography and stereology both seem to be words for the science of medical scanning. (Question 2 should make the connection with integral geometry plausible: lines being fired through a body…) At the recent meeting on integral geometry in Barcelona, someone patiently explained to me that they were very different, but I’m afraid I’ve forgotten what that difference is.

Posted by: Tom Leinster on November 30, 2010 4:02 PM | Permalink | Reply to this

Re: What is Integral Geometry?

Gardner’s book, in the preface and some chapter end notes (in the second edition anyway; Google books has only the first) sheds some light on the tomography/stereology distinction without completely clearing it up. Some quotes:

The title of this book, Geometric Tomography, is designed to cover the area of mathematics dealing with the retrieval of information about a geometric object from data about its sections, or projections, or both.

[Stereology and geometric probing] each have their own distinct viewpoint, while sharing common features with geometric tomography. For example, stereology focuses on random data and statistical methods, but also draws on integral geometry.

Stereology … deals with a body of methods for the exploration of three-dimensional space, when only two-dimensional sections through solid bodies or their projections on a surface are available. [Apparently due to H. Elias]

The probablistic or statistical nature of stereology sets it apart from geometric tomography. However, there is some overlap. For example, stereology makes heavy use of kinematic formulas … and these are intimately related to formulas of central importance in geometric tomography.

Posted by: Mark Meckes on November 30, 2010 4:32 PM | Permalink | Reply to this

Re: What is Integral Geometry?

It’s probably the same thing that’s explained here here.

It’s also worth noting that due to “noise” (whether it’s genuine noise or something about the real world that’s not included in your model), most actual 3-D reconstruction algorithms tend to eschew sophisticated analytic relations for doing optimisation over potential reconstructions, using a probabilistic generative model to “score” how likely a given structure is given it’s 2-D data (of whatever variety).

Posted by: davetweed on November 30, 2010 5:39 PM | Permalink | Reply to this

Re: What is Integral Geometry?

You should check out the book Geometric Tomography by Richard Gardner (which has some nice pictures illustrating intrinsic volumes) for the connections here.

Posted by: Mark Meckes on November 30, 2010 4:08 PM | Permalink | Reply to this

Re: What is Integral Geometry?

Think there was some simultaneous posting there… Actually, it was Mark who put me onto Gardner’s book.

Posted by: Tom Leinster on November 30, 2010 4:12 PM | Permalink | Reply to this