The method we are going to use to solve our differential equation and thus the air-flow is what is called a finite-volume method. We view space as being broken down into a set of volumes each of which surrounds one of our points. In particular the volume associated with each point is the region of space that is closer to that point than to any other point. Breaking space into such cells is called the Voronoi Diagram of a set of points. In a Voronoi diagram we have exactly one cell per point. As an example, here is a set of points along with their Voronoi cells:

Note that each cell is a convex polygon (except for boundary points which are a partial polygon), and each edge of the polygon fall half way between two points. If we draw the line between every pair of such points we get what is called the Delaunay triangulation of the points. In our solution we will consider both the Voronoi edges and the Delaunay edges.

We now consider how we can use these cells to solve our fluid flow problem. The way to think about it is to consider the total flow that enters a cell through its boundaries. I claim that the net flow (sum of flow in and out) has to be zero. Intuitively this is because the fluid (or air) has no where to go. This condition can be written formally as:

where is the boundary of the cell is our flow (the gradient of ) and is the vector normal to the surface. It turns out that if we consider all possible boundaries then this definition is equivalent to Laplace's equation (equation 1).

The way we specify that the net flow into each cell is 0 is by writing a linear equation for each cell. The variables in these equations are going to be the values of our function at the points (these are the variables we want to solve for). If we have cells, we are going to write equations. Since there are unknowns we can simply solve the set of linear equations. We discuss how to solve these equations later but first discuss how to generate the equations.

Thu Jun 15 17:00:37 EDT 1995