Constant Time Algorithms for Triangulation of Simple Polygons on Reconfigurable Mesh
Wan Ying · Chinese Journal of Computers · 2002
Triangulation of simple polygons is one of the fundamental problems in computational geometry, and has many important applications in computer graphics, geographical information systems, finite element methods, and many other fields. The reconfigurable mesh consists of an array of processors interconnected by a reconfigurable bus system. The bus system can be used to dynamically obtain various interconnection patterns among the processors. Recently, this model has attracted a lot of attention. The main contribution of this paper is to exploit the advantage of the model to obtain efficient algorithms for triangulation of simple polygons and monotone polygons. First we propose a sequential algorithm to divide a simple polygon to some disjoint special monotone polygons, and obtain a constant time algorithm to divide a monotone polygon to disjoint special monotone polygons on an n×n reconfigurable mesh based on it, where n is the number of points of the input polygon. Then we divide the reconfigurable mesh into some submeshes corresponding to the special monotone polygons, and assign each special monotone polygon to one submesh. Because these submeshes can execute the algorithm in parallel and a constant time algorithm to triangulate a special monotone polygon on the reconfigurable mesh has been proposed by Bokka et al., so we get an algorithm to triangulate a monotone polygon in O(1) time on an n×n reconfigurable mesh. By generalizing these algorithms and using a little more processors, we obtain another algorithm to triangulate a simple polygon in O(1) time on an n×n 1+e reconfigurable mesh, where 0 e 1 is a constant. To the best of our knowledge, this is the first time that constant time solutions to triangulation of monotone polygons and simple polygons are reported. We also believe that the methods proposed in the paper can be used to design efficient parallel algorithms for other problems in computation geometry.