A Box Algorithm (Box)

Overview

This algorithm locates a level set of an arbitrary function from R^n -> R, although only the dimensions n=2 and n=3 are implemented. It should locate all components of the level set that are sufficiently large, but will typically misrepresent the topology of a level set in the vicinity of a singularity.

How the Box Algorithm Works

For functions of two variables, the Box Algorithm locates the zero set of a function by breaking the domain into a fixed set of rectangular cells. For each square in the grid, look along the edges of the square for zeros of the function. This is done by evaluating the function at the corners of the square and looking for edges that have a sign change; provided the function is continuous, there will be a zero somewhere along such an edge. The position of the zero is approximated using the values of the function at the corners via linear interpolation. Once the positions of the zeros along the edges of the squares are located, these zeros are joined by line segments through the interior of the square. Taken over all the squares in the grid, these line segments represent an approximation to the actual zero set of the function. To get a better approximation, one uses a finer grid. See the explanation of the so-called simple algorithm to get a more complete description of the geometry behind the two-variable case.

For functions of three variables, the process is similar, except that cells are now cubes. We linearly approximate the zero set by finding points on each cell edge that are approximately zero, and then we connect these points with a polygon. The surface is formed as the union of these polygons.

The panel that controls the box algorithm.

Controlling the algorithm from Pisces

Detail: The box algorithm uses a uniform subdivision of the bounding box into cells. The computational domain will be divided into Detail^n cells, n=2,3.

Known Bugs

None. Please send bug reports to software@geom.umn.edu.)

Acknowledgements

The algorithm was implemented by Daniel B. Krech, who was supervised by Davide Cervone.

Next: A Simple Algorithm
Previous: User Interface

The Pisces Home Page