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

Computational Geometry on the Broadcast

Communication Model

**Chang-Biau Yang**

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 , 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 time.

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

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.