The problem of computing the convex hull of a set of vectors in the two-dimensional plane is considered from the point of view ot parallel implementation on transputer networks. A parallel algorithm is described, timed and evaluated against tunctionally equivalent single processor code. The results of these numerical experiments are presented and discussed. geometric computing, parallel implementation, convex hull, transputers Geometric computing is widely recognised as an ideal problem domain for parallel processing 1'2. Problem domains for geometric computation include computeraided engineering design and image processing. Many problems in geometric computation are computebound and one solution is to design special hardware, for particular tasks, to improve the performance. This approach, however, tends to be inflexible and is expensive to update, generalize or reconfigure -it becomes economic to do this only when algorithms for the problem are well established and unlikely to be significantly improved upon.
Alternatively, software solutions are feasible using reconfigurable general purpose parallel processing systems to meet the computational demands of these, and similar, applications. The software approach, which this paper addresses, lends itself more readily to rapid prototyping, incremental development and optimization.
Until recently, however, the availability of readily usable and affordabl e parallel processing systems had not been wide; but the advent of the Inmos transputer, and other similar microcomputer chips, has led to a proliferation of relatively inexpensive workstations with reconfigurable parallel processing subsystems. These novel systems provide an opportunity to design and compare parallel algorithms for a wide variety of application areas that include geometric computing. Variations in the structure of algorithms can be investigated to optimize performance for different transputer configurations, matching algorithm design and network topology. In this paper, some experimental work is described on the parallel implementation, on a transputer-based workstation, of an algorithm for the computation of convex hulls. It should be noted that the convex hull computation is closely related to sorting, into which it may be linearly transformed 3.