The authors consider the problem of reducing the number of polygons in a mesh. They introduce a linear grouping technique that is based on the idea of finding groups of nearly collinear vertices, and replacing them by one line segment. A group of vertices is considered as nearly collinear if they all fall within &egr; of a line. The effective values for &egr; are in the range 0.5 percent ≤ &egr; ≤ 1.5 percent.

To find good groupings, the authors use a branch-and-bound algorithm with best-first order. They introduce bounds and heuristics that reduce the number of considered groupings, and thus speed up the algorithm.

Reducing the vertices of a mesh is important for graphical model rendering in real-time. According to the authors, for &egr; = 0.5 percent, the number of vertices is reduced on average 55 percent. Execution time is in seconds for meshes with less than 300 vertices, and in minutes for meshes with up to 700 vertices.

The paper is rather brief, and does not provide many details about the number of experiments done. However, the authors provide a Web site containing the implementation of the algorithms in C++ for both the UNIX and Windows operating systems. The paper may be of interests to programmers developing real-time applications.