A triangulation for optimal strip decomposition in simple polygons
Siu-Wing Cheng, Jae-Sook Cheong · 1999
In computer graphics, most polygonal surfaces are rendered via triangles. Rendering a set of triangles needs the data of the triangle vertices. Since the speed of rendering is bounded by data rate, reducing the amount of data will make rendering faster. This can be attained by ordering triangles so that consecutive triangles share an edge, that is, only one additional vertex need to be transmitted to describe each triangle. There exists such an order if and only if the dual graph of the triangulation contains a Hamiltonian path. Many polygons, however, do not have Hamiltonian triangulation; they can not be triangulated into a single triangle strip. Triangle strip is a set of triangles whose dual is a Hamiltonian path. This paper introduces an algorithm to construct a triangulation that can be decomposed into minimum number of triangle strips in simple polygons. This algorithm uses dynamic programming techniques and has O(n 3) time bound.