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

Journal of Inforamtion Science and Engineering, Vol.15 No.3, pp.383-395 (May 1999)
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, k3, our ranking algorithm requires JISE time.

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

Full Text () Retrieve PDF document (199905_04.pdf : 70,163 bytes)

Received April 11, 1996; accepted May 1, 1998.
Communicated by Wen-Lian Hsu.
*This research work was partially supported by the National Science Council of the Republic of China under contract NSC-82-0208-M-110-027.