Motivated by applications in computer graphics, we study the problem of computing an optimal encoding in "triangle strips" of a triangulation of a polygonal surface model. The goal is to facilitate the transmission and rendering of a polygonal model by decomposing its triangulation into a minimum number of "tristrips," each of which has its connectivity stored implicitly in the ordering of the data points. While this optimization problem has been conjectured to be hard, its complexity status has been open. We prove that the tristrip decomposition problem is, in fact, NP-complete. We also propose two methods for solving the problem to optimality, one based on an integer programming formulation, one based on a branch-and-bound scheme that relies on lower bounding techniques for its efficiency. We perform an extensive set of experiments to test the efficiencies of these methods and some of their variants. These methods have been integrated also with the practical system FTSG (Fast Triangle Strip Generator), in order to utilize optimization methods on small subproblems to improve the quality of the heuristic solutions obtained by FTSG. We use experimentation to judge the quality of the improvements.

We study the problem of simplifying a polygonal subdivision, subject to a given error bound, , and subject to maintaining the topology of the input, while not introducing new (Steiner) vertices. In particular, we require that the simpli- ed chains may not cross themselves or cross other chains. In GIS applications, for example, we are interested in simplifying the banks of a river without the left and right banks getting \\tangled" and without \\islands" becoming part of the land mass. Maintaining topology during subdivision simplication is an important constraint in many real GIS applications. We give both theoretical and experimental results. (a). We prove that the general problem we are trying to solve is in fact dicult to solve, even approximately: we show that it is MIN PB-complete and that, in particular, assuming P 6= NP, in the general case we cannot obtain in polynomial time an approximation within a factor n 1=5 of an optimal solution. (b). We propose some heuristic methods for solving the problem, which we have implemented. Our experimental results show that, in practice, we get quite good simplications in a reasonable amount of time. Keywords polygonal subdivisions, simplication, map generalization, geographic information systems, approximation algorithms 1.