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.
CS Dept TR Overview