wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> Convex Set Projection 
        
(Message started by: william wu on Nov 5^th, 2003, 7:01pm)

Title: Convex Set Projection
Post by william wu on Nov 5^th, 2003, 7:01pm

Prove the following beautiful theorem:

The expected projected area of a convex set S is 1/4 the surface area of S.

(these hints outline an approach you can use)

Hint 1: [hide]Think about the expected projection of a single line segment of length L. (this calculation should not be difficult)[/hide]

Hint 2: [hide]With your work with respect to Hint 1 in mind, think about the line segments that make up a convex polygon. Consider the projections of a convex polygon.[/hide]

Note: (background)

1. "A set S in n-dimensional space is called a convex set if the line segment joining any pair of points of S lies entirely in S." - Mathworld

2. It is implied that the plane onto which we are projecting is chosen uniformly at random. So you can think of the plane's normal vector as a random variable.

3. Visually what is happening: Think of some egg-shaped ellipsoid (an example convex set) hovering in 3d space. Then you pick a 2D plane to place on one side of the egg. Now you shine a flashlight from the opposite side. This casts a shadow onto the plane. The area of this shadow is the "projected area" of the egg. The theorem says that if you average the areas you would get by considering all possible orientations of 2d planes to project on, the result will be one-fourth of the surface area of the egg! :o It is quite amazing if you contemplate it for a while. You can have very different convex sets, such as flat triangles vs. solid spheres, and as long as they have the same surface area, the average projected area will be the same.

Title: Re: Convex Set Projection
Post by James Fingas on Dec 10^th, 2003, 6:44am

The average projected area of a convex set can be considered to be the sum of the average projected areas of each of its facets. Each facet projects area over exactly half of a sphere, reaching its maximum area when face-on and decaying as the cosine of the angle between the normal to the facet and the normal to the projected plane.

We must average this over the entire hemisphere, normalized by solid angle. I will assume the facet has unit one-sided surface area and faces up. A plane is defined by the zenith [phi] (angle between vertical and the plane normal) and azimuth [theta] (90 degrees minus the angle between "North" and the cross product of vertical and the plane normal). These are probably not exactly the right definitions, but they're close enough for me!

[int] cos[phi] dA / [int] dA

where dA is the differential area of the unit hemisphere (aka solid angle), which is d[theta]sin[phi]d[phi] I think.

[int][int] cos[phi]sin[phi] d[theta]d[phi] / [int] sin[phi] d[theta]d[phi]

Now we could evaluate this the hard way, or we could notice that this is also the projection of the hemisphere onto the plane defined by the facet! That is just equal to the area of a circle, [pi]. The [int] dA is equal to 2[pi], but notice that the facet is only visible through half the sphere of view, so the average projection from the facet is equal to [pi]/2[pi]/2 = 1/4.

The projection of the convex set is the sum of the projections of its facets, and the surface area of the convex set is the sum of the surface areas of its facets.

QED!