@TECHREPORT{R-96-38,
NUMBER = {R-96-38},
INSTITUTION = ida,
ADDRESS = idaaddr,
YEAR = {1996},
AUTHOR = {Fj{\"a}llstr{\"o}m, Per-Olof},
TITLE = {PARALLEL ALGORITHMS FOR GEOMETRIC PROBLEMS ON COARSE GRAINED MULTICOMPUTERS},
ABSTRACTURL = {/publications/cgi-bin/tr-fetch.pl?r-96-38+abstr},
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.}