JISE


  [1] [2] [3] [4] [5] [6] [7] [8] [9] [10]


Journal of Information Science and Engineering, Vol. 15 No. 3, pp. 383-395


Computational Geometry on the Broadcast Communication Model


Chang-Biau Yang
Department of Applied Mathematics 
National Sun Yat-Sen University 
Kaohsiung, Taiwan 804, R.O.C.


    In this paper, we solve three geometric problems, including the ranking, convex hull and closest pair problems, under the broadcast communication model. To solve these problems, we propose a general scheme, the p-division approach, which is based upon the divide-and-conquer strategy. In the 2-dimensional space, the time complexities of our algorithms for solving these problems are all JISE, where n is the number of input points and p is the number of processors used. Furthermore, our algorithms are all conflict-free and optimal. In the k-dimensional space, k≧3, our ranking algorithm requires JISE time.


Keywords: broadcast communication, computational geometry, parallel algorithm, divide-and-conquer, conflict-free

  Retrieve PDF document (JISE_199903_04.pdf)