IDA Technical Reports: abstract

Fjällström, P.-O. (1996). PARALLEL ALGORITHMS FOR GEOMETRIC PROBLEMS ON COARSE GRAINED MULTICOMPUTERS. Technical Report LiTH-IDA-R-96-38, Department of Computer and Information Science, Linköping University, Sweden. (bibtex),

Abstract: We present scalable parallel algorithms for some geometric problems on coarse grained multicomputers. More specifically, for a square mesh-connected p-processor computer, we show that: 1.  The all-farthest-neighbors problem for a convex n-gon can be solved  in O(n/p) time, if n p2/4. 2.  The maximum-perimeter triangle inscribed in a convex n-gon can  be found in O(n(log (n/p) + log2 p)/p) time, if n p2. 3.  If n p2, the two-dimensional batched range-searching problem  (n  points/queries) can be solved in  O((n log n log p + k)/p + Ts(n log p, p)) time,      where k is the number of reported points and Ts(m,p) is the time to sort m items on a p-processor computer. The two first results are based on the formulation of these problems as searching problems in totally monotone matrices.