Some Geometric Problems on OMTSE Optoelectronic Computer

Abstract

Optical Multi-Trees with Shuffle Exchange (OMTSE) architecture is an efficient model of an optoelectronic computer. The network has a total of $3n^3/2$ nodes. The diameter and bisection width of the network are $6 \log n -1$ and $n^3/4$ respectively. In this note, we present synchronous SIMD algorithms on an OMTSE optoelectronic computer for the following problems in computational geometry: Convex Hull, Smallest Enclosing Rectangle, All-Farthest/All-Nearest Neighbors, Closest/Farthest pair, Maximal Points. The strength of the proposed algorithms over the existing algorithms on OMULT has also been discussed.