Efficient parallel geometric algorithms on a mesh of trees

ABSTRACT

In this paper, we present some efficient parallel geometric algorithms for computing the All Nearest Neighbors, Delaunay Triangulation, Convex Hull, and Voronoi Diagram of a point set S with N points in the plane. The algorithm of All Nearest Neighbors is to find the nearest-neighbor point for each point in S. It can be applied to cluster analysis, classification theory and computational geometry. A Delaunay Triangulation of S is an triangulation in which the circumcircle of each triangle contains no any other point of S. Delaunay Triangulation has practical applications on finite-element method, computational fluid dynamics, geometric modeling, visualization, numerical analysis, and computational geometry. The Convex Hull of S is the smallest convex polygon that includes all the points of S. Convex hull has many applications in pattern recognition, image processing, stock cutting and allocation, and computational geometry. The straight-line dual of a Voronoi Diagram is a Delaunay Triangulation. Voronoi Diagram is a very useful data structure for robotics, image processing, graph theory, computational fluid dynamics, and computational geometry. We use a mesh of trees with N × N processors as the computation model. All of these parallel algorithms have the same good time complexity O (log N) [1][9].

REFERENCES

• 1: Selim G. Akl , Kelly A. Lyons, Parallel computational geometry, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• 2: B. Chazelle, "Computational Geometry on a Systolic Chip", IEEE Transactions on Computers, Vol. C-33, No. 9, Sept. 1984, pp774--785.
• 3: D. J. Evans and I. Stojmenovic. "On Parallel Computation of Voronoi Diagrams", Parallel Computing, Vol. 12, 1989, pp121--125.
• 4: C. -S. Jeong, "An Improved Parallel Algorithm for Constructing Voronoi Diagram on a Mesh-Connected Computer", Parallel Computing, Vol. 17, July 1991, pp505--514.
• 5: Fenglien Lee and S. Q. Zheng, "Constructing Voronoi Diagram of a Point Set on Mesh of Trees", International Conference on Parallel Processing, Vol. III, 1992, pp136--140.
• 6: F. Thomson Leighton, Introduction to parallel algorithms and architectures: array, trees, hypercubes, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1991
• 7: P. D. MacKenzie and Q. F. Stout, "Asymptotically Efficient Hypercube Algorithms for Computational Geometry", Proceedings of the Third Symposium on the Frontiers of Massively Parallel Computation, October 1990, pp8--11.
• 8: R. Miller , Q. F. Stout, Mesh Computer Algorithms for Computational Geometry, IEEE Transactions on Computers, v.38 n.3, p.321-340, March 1989 [doi>10.1109/12.21120]
• 9: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• 10: Sanjeev Saxena , P. C. Bhatt , V. C. Prasad, Efficient VLSI Parallel Algorithm for Delaunay Triangulation on Orthogonal Tree Network in Two and Three Dimensions, IEEE Transactions on Computers, v.39 n.3, p.400-404, March 1990 [doi>10.1109/12.48871]
• 11: I. Stojmenovic, "Computational Geometry on a Hypercube", Proceedings of the 1988 International Conference on Parallel Processing, August 1988, Vol. III, pp100--103.
• 12: Cao An Wang , Yung H. Tsin, An O(log n) time parallel algorithm for triangulating a set of points in the plane, Information Processing Letters, v.25 n.1, p.55-60, 20 April 1987 [doi>10.1016/0020-0190(87)90093-7]

INDEX TERMS

Keywords:
Delaunay triangulation, Voronoi diagram, all nearest neighbors, computational geometry, convex hull, mesh of trees, parallel algorithm