Iterative algorithms for convex hull, triangulation, and other problems on mesh-connected arrays

This thesis presents new sequential and parallel algorithms for several important problems in computational geometry, using an iterative paradigm related to dynamic programming and greedy models of algorithm design. The two primary problems studied are the convex hull and triangulation of points in k-space.; Previous sequential algorithms for these problems are surveyed, and new sequential algorithms are presented for planar convex hull and Delaunay and greedy triangulation in the plane. Algorithms for Delaunay triangulation in k-space are derived from the planar triangulation algorithms. Finally, it is shown how these algorithms can be adapted to solve convex hull and Voronoi diagram in k-space.; Corresponding parallel algorithms are also developed. Previous work on parallel algorithms is surveyed. Algorithms for planar convex hull, Delaunay and greedy triangulation in the plane and Delaunay triangulation in k-space are given for several mesh models. Again, it is shown how these algorithms can be adapted to solve convex hull, all nearest neighbors, and Voronoi diagram in k-space. Experimental results are shown for the planar convex hull algorithms implemented on an Intel NCUBE.; None of the algorithms given in this thesis uses the divide-and-conquer method as do most previous such algorithms. The paradigm used to develop these algorithms is described and discussed. An example is given of another problem which is amenable to this method. In the conclusions, prospects for further research in this area are evaluated.