I was thinking about a question that Eric Haines posed to me at SIGGRAPH and came across a particularly satisfying fallacy in the process.  I’ll talk about Eric’s question in a later post, and explain what it has to do with fast rendering (specifically acceleration structure construction heuristics).

circleandsquare

For now, I would like to convince you that the perimeter of a circle with radius 1 is exactly 8.  However, before I attempt such an outrageous feat, I’ll show you a convenient method to approximate the area of a circle.  To begin, we will construct a square enclosing our circle.  We can compute the area of this square, 4, as a very crude approximation of the area of our circle of radius 1.  

Next, we will make a better approximation.  Divide the square into 4 smaller squares, and then divide each of these squares into 4 smaller squares, and so on.  After subdividing n times, we will have 4^n squares each with area 1/4^{n-1}.  If we then throw away all of the squares that don’t cover any part of the circle, we’ll arrive at successively better approximations to the shape of the circle, as well as its area.  This approach to approximating the area of a circle is a quite literal example of quadrature.

two and three levels of subdivision

We can use this same approximation to the circle to show that it’s perimeter is exactly 8 units long.  First consider our original square, whose perimeter is 8 units long.  Amazingly, even after subdividing a few times, the perimeter of our remaining squares is still exactly 8 units long.  Since further subdivision makes this bounding curve into a better and better approximation of the circle, while keeping its length fixed, the circle’s boundary (aka. its perimeter) must also be exactly 8 units long.

perimeter

What’s wrong here?  Or to be even more pointed, why does the proposed quadrature method work for approximating the area of a circle, but not work for approximating its perimeter?

I thought I knew a satisfactory answer to this question, but upon deeper reflection I realized I have no clue.  One cursory answer to the question is to point out that just because something is true for every element of a sequence does not mean it is still true in the limit.  While true, this answer doesn’t also explain why the quadrature method above works to approximate the area.

Since I don’t want to leave you empty handed, I’ll pass along a theorem I read that’s useful for designing quadrature methods that work.

Theorem

Let R_n be a sequence of convex figures converging upon the convex figure L.  Then the perimeters and areas of the sequence converge on the perimeter and area of L.  That is,

if R_n\to L all convex, then \mu(R_n)\to\mu(L)

where \mu stands for either the perimeter or area of the figure.

A good example of such an approach is to approximate the circle by enclosing regular polygons, P_n, where n stands for the number of sides.  Even a crude approximation of our circle by a hexagon yields approximate area 3.1547 and approximate circumference 6.9282, a much better guess than 8.

Advertisements