Find min and max the best possible way
Victor is a graduate student at North Carolina State University majoring in electrical and computer engineering with a minor in computer graphics. He can be reached at 1001 Japonica Court, Knightdale, NC 27545; or via e-mail [email protected].
Extents are often used in computer graphics and constructive solid geometry where the edges of the smallest, axes-aligned rectangle enclosing an object are the extents of that object. In two-dimensional space, this is also called "boxing" and in three-dimensional it is a "three-dimensional (3-D) rectangle" -- a parallelpiped.
Graphical objects are often defined by a set of vertices (points) in three dimensions. Finding extents of an object defined by a set of points is a simple process once you realize that the extents are the minimum and the maximum of the object in every dimension. To find the minimum (or maximum) X coordinate, you must search the vertex list that defines the object. The well-known algorithms find_min and find_max are used to accomplish this (see Listing One, page 102). The procedure is then repeated for Y and Z dimensions.
If an object is defined by N vertices, this approach takes (N -1) comparisons to find the Xmin, (N -1) comparisons to find the Xmax, and so on, for a total of 6 (N -1) comparisons for a 3-D object. However, is this the minimal number of comparisons? It's been shown that (N -1) comparisons are necessary to determine the minimum (or the maximum) of N items.1 In other words, the algorithms find_min and find_max in Listing One are optimal and it is not possible to do any better by comparison of items! If you were to perform fewer than (N -1) comparisons, an incorrect answer would result for the same input. Yet, it is possible to perform fewer comparisons if both the minimum and maximum are needed, as is the case with object extents.
When minimizing the amount of work done by two separate operations -- searching for minimum and maximum in our case -- the usual technique is to look for any work or intermediate results that can be shared. In this case there does not seem to be any shared work; the find_max procedure compares all of the points to max and the find_min procedure compares all of the points to min. In many cases it may be beneficial to sort the list of items, or a sublist of items. Sorting the whole list makes things worse, because sorting is a slower order operation, O(NlogN), than finding a minimum or a maximum, O(N).1 However, sorting two items helps minimize the work since this takes only a single comparison.
The strategy used to find the extents is as follows (see the find_min_max procedure in Listing Two, page 102):
- 1. Compare the first two items to each other. Place the larger in max and the smaller in min.
- 2. Take the next two items and compare them to each other. Then compare the larger item to max and the smaller item to min. If the larger item is larger than max place it in max. If the smaller item is smaller than min place it in min.
- 3. Take care of the last item if the number of items is odd. If this item is greater than max it can not be smaller than min, so there is no need to compare to min.
This procedure is slightly more complex, but the gains are dramatic. In fact, to find the minimum vertex and the maximum vertex in the X dimension for an object with N vertices (3N/2 -2) comparisons will be performed by find_min_max if N is even, and (3N/2-3/2) comparisons if N is odd. In contrast, 2(N -1) comparisons will be done by find_min and find_max. This amounts to a savings of approximately 25 percent. What is most important about this result is that it has been shown to be optimal!1 In other words, it is not possible to make any fewer comparisons of items! What's more, the find_min_max procedure is general purpose and can be used in many other applications.
Application
As one example of computational savings, let's apply the find_min_max procedure to a polygon clipping test. Assume that 100,000, 4-vertex polygons need to be displayed per second.2 Each of the polygons must be tested to see if it falls completely inside of the display window's boundaries which are 3-D boundaries. Each polygon must be handled separately since no relationship can be assumed between polygons in general. There are three possible ways to handle this:
- 1. The vertices of each polygon could be tested to see if all of them fall within the 3-D display window. This implies that 400,000 vertices must be checked against two boundaries in each dimension (for example, window_x_min and window_x_max), or six comparisons per vertex. In other words, this requires 2,400,000 comparisons per second, or 2.4 Mflops.2
- 2. Extents (min and max) of each polygon could be found and compared to the window boundaries. This implies 2(4 -1) comparisons per dimension, plus a comparison of min to the window minimum and of max to the window maximum -- a total of eight comparisons per dimension. Therefore, 24 comparisons per polygon would have to be made, or 2.4 Mflops (as before).
- 3. Perform (3*4/2-2) or four comparisons per dimension plus the two comparisons to the window boundaries, for a total of six comparisons per dimension. Therefore, 18 comparisons would be made per polygon, or 1.8 Mflops. This is a savings of 0.6 Mflops, or 25 percent of 2.4 Mflops.
This example demonstrates that valuable computing resources are being wasted by performing redundant work using the first two methods.
Benchmarks
The MIN/MAX algorithm was benchmarked on several computer systems using lists of floating-point numbers of various lengths. The results are summarized in Table 1. Note that the MIN/MAX algorithm delivers more than the promised 25 percent speedup, on the majority of the systems tested. Since the algorithm performs fewer comparisons, it performs fewer stores (writes) of items to min and max. In fact, the number of writes is potentially reduced in half, as each item is compared to either min or max, but never both, in the MIN/MAX algorithm. This may reduce bus traffic in some systems.
Table 1: Results of MIN/MAX algorithm
Machine MIN/MAX MIN & MAX Speed up --------------------------------------------------- PC/AT 8 MHz 600,000 items 34.82 sec. 48.20 sec. 27.8% VaxStation2000 1,200,000 items 13.70 sec. 18.70 sec 26.7% DEC 3100 24,000,000 items 17.30 sec. 32.70 sec. 47.1% Sun SparcStation 24,000,000 items 50.70 sec. 66.60 sec. 23.9% Cray Y-MP 60,000,000 items 30.21 sec. 43.97 sec. 31.3%
The method described is applicable to computational environments where a comparison is a binary operation. Most of today's sequential software environments satisfy this condition. However, it is possible to build hardware to find the min and the max of a fixed number of items in a single step.
References
- 1. S. Baase. Computer Algorithms: Introduction to Design and Analysis, second edition, Reading Mass:, Addison-Wesley, Nov. 1988, pp. 24-26, pp. 125-128.
- 2. K. Akeley and T. Jermoluk. "High-Performance Polygon Rendering," SIGGRAPH, Computer Graphics, vol. 22, no. 4, August 1988.
_OPTIMAL DETERMINATION OF OBJECT EXTENTS_ by by Victor J. Duvanenko, W.E. Robbins, and Ronald S. Gyurcsik
[LISTING ONE]<a name="0202_0008">
/* min.c -- Procedure to find the smallest element of the array.
The number of elements in the array must be > 0. ( n > 0 ) */
float find_min( array, n )
float array[]; /* input array */
int n; /* number of elements in the array ( n > 0 ) */
{
register i; float min;
min = array[0];
for( i = 1; i < n; i++ )
if ( min > array[i] ) min = array[i];
return( min );
}
/* Procedure to find the largest element of the array.
The number of elements in the array must be > 0. ( n > 0 ) */
float find_max( array, n )
float array[]; /* input array */
int n; /* number of elements in the array ( n > 0 ) */
{
register i; float max;
max = array[0];
for( i = 1; i < n; i++ )
if ( max < array[i] ) max = array[i];
return( max );
}
<a name="0202_0009"><a name="0202_0009">
<a name="0202_000a">[LISTING TWO]<a name="0202_000a">
/* min_max.c -- Procedure to find the smallest and the largest element of
the array. The number of elements in the array must be > 0. ( n > 0 ) */
void find_min_max( array, n, min, max )
float array[]; /* input array */
int n; /* number of elements in the array ( n > 0 ) */
float *min, *max; /* pointers to the return values */
{
register i;
if ( n <= 1 )
*min = *max = array[0];
else {
if ( array[0] > array[1] ) { /* establish the basis min and max */
*max = array[0];
*min = array[1];
}
else {
*max = array[1];
*min = array[0];
}
for( i = 2; ( i + 2 ) <= n; i += 2 )
if ( array[ i ] > array[ i + 1 ] ) {
if ( array[ i ] > *max ) *max = array[ i ];
if ( array[ i + 1 ] < *min ) *min = array[ i + 1 ];
}
else {
if ( array[ i + 1 ] > *max ) *max = array[ i + 1 ];
if ( array[ i ] < *min ) *min = array[ i ];
}
if ( i < n ) /* handle the odd/last array element */
if ( *max < array[i] ) *max = array[i];
else if ( *min > array[i] ) *min = array[i];
}
}