**Dept. of Computer and Information science, Linköping University**

## IDA Technical Reports: abstract

*Generated: Thu, 24 Apr 2014 16:50:29 *

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.

**Goto (at Linköping University):**
```
CS Dept
TR Overview
```

*<webmaster@ida.liu.se>*