A parallel algorithm of constructing a Voronoi diagram on hypercube connected computer networks

Chai, Wenmao (1994) A parallel algorithm of constructing a Voronoi diagram on hypercube connected computer networks. Masters thesis, Memorial University of Newfoundland.

[English] PDF (Migrated (PDF/A Conversion) from original format: (application/pdf)) - Accepted Version Available under License - The author retains copyright ownership and moral rights in this thesis. Neither the thesis nor substantial extracts from it may be printed or otherwise reproduced without the author's permission. Download (11MB) [English] PDF - Accepted Version Available under License - The author retains copyright ownership and moral rights in this thesis. Neither the thesis nor substantial extracts from it may be printed or otherwise reproduced without the author's permission. (Original Version)

Abstract

Computational geometry is a branch of computer science concerned with the design and analysis of algorithms to solve geometric problems. The Voronoi diagram of a set S of n points (called sites) is a well known structure in computational geometry. In the Voronoi diagram, each point is surrounded by a convex polygon enclosing that territory which is closer to the surrounded point than to any other point in the set. Voronoi diagrams are useful in solving geometric problems such as proximity problems and the Euclidean minimum spanning tree problem. Voronoi diagrams also have applications in diverse areas like biology, visual perception, physics, and archeology. -- There exist many methods to construct Voronoi diagrams on a single computer. Two of them are proposed by Shamos and Brown. In 1975, Shamos applied two-dimensional Voronoi diagrams to obtain elegant solutions in computational geometry, such as finding the nearest neighbor and construction of minimum spanning trees. Shamos described an O(n log n) time sequential algorithm to construct the planar Voronoi diagram for a set of planar points. The strategy he used in the serial algorithm is divide-and-conquer. In 1979, Brown demonstrated an interesting linkage between the Voronoi diagram and the convex hull. He presented an O(n log n) algorithm for constructing the Voronoi diagram, by transforming the problem of constructing a planar Voronoi diagram for an n-points set to the construction of a convex hull of n points in 3-dimensional space via a geometric transformation known as inversion. -- Due to the nature of some applications in which geometric problems arise, fast and even real-time algorithms are often required. Here, as in many other areas, parallelism seems to hold the greatest promise for major reduction in computation time. The idea is to use several processors which cooperate to solve a given problem simultaneously in a fraction of the time taken by a single processor. Therefore, it is not surprising that the interest in parallel algorithms for geometric problems has grown in recent years. -- Based on Shamos's and Brown's methods, several parallel algorithms to construct Voronoi diagrams have been presented. Some of them are implemented on parallel random access machines. Some of them are run on processor networks such as mesh, cube-connected cycles, stars and pancakes. We will discuss them in the literature review. With the development of communication technique and concurrent programming, computer networks have become popular. The most popular processor interconnection topology today is undoubtedly the hypercube. Hypercubes have several advantages. First, the number of nodes in a hypercube grows exponentially with the number of connections per node, so that a small increase in the hardware at each node allows a large increase in the size of the computer. Second, the number of alternative paths between nodes increases with the size of the hypercube, which helps relieve congestion. Third, efficient algorithms are known for routing messages between processors in a hypercube. Finally, and today most importantly, a large corpus of software and programming techniques exists for hypercube. -- The hypercube is one of the most versatile and efficient networks yet discovered for parallel computation. In this thesis, a single instruction multiple data stream hypercube connected computer network is chosen as our parallel computation model. In a hypercube connected computer network, local computations as well as message exchanges are taken into consideration when analyzing the time taken by the processor networks to solve a problem. Based on Nassimi and Sahni's paper fundamental operations on hypercube connect computer networks are descriptively discussed. The corresponding programs are also given. Based on Brown's approach, a parallel algorithm to construct Voronoi diagrams are developed. Our algorithm runs in O(log³n) time on an O(n)-processor hypercube connected computer network. Our algorithm has several advantages. First, our algorithm is based on Brown's method which transforms the problem of construction of a planar a Voronoi diagram for an n-point set to construction of a convex hull of n points in three dimensional space. Compared with the parallel algorithms which are based on the divide-and-conquer approach used by Shamos, our algorithm can be used to solve two computational geometry problems: constructing 2—dimensional Voronoi diagrams and 3—dimensional convex hulls. Second, comparing with Chow's methods which runs on a O(n) processors CCC (Cube-Connected Cycles) model has O(log⁴n) time complexity, our algorithm has better time complexity. Third, comparing with Chang-Sung Jeong's algorithm which runs in O(√n) on an √n x √n mesh, our parallel computation model is more general because most other popular networks can be easily mapped onto a hypercube.

Actions (login required)

View Item