SCALABLE ALGORITHMS FOR BICHROMATIC LINE SEGMENT INTERSECTION PROBLEMS ON COARSE GRAINED MULTICOMPUTERS

We present output-sensitive scalable parallel algorithms for bichromatic line segment intersection problems for the coarse grained multicomputer model. Under the assumption that n≥p², where n is the number of line segments and p the number of processors, we obtain an intersection counting algorithm with a time complexity of , where T_s(m, p) is the time used to sort m items on a p processor machine. The first term captures the time spent in sequential computation performed locally by each processor. The second term captures the interprocessor communication time. An additional time in sequential computation is spent on the reporting of the k intersections. As the sequential time complexity is O(n log n) for counting and an additional time O(k) for reporting, we obtain a speedup of in the sequential part of the algorithm. The speedup in the communication part obviously depends on the underlying architecture. For example for a hypercube it ranges between and depending on the ratio of n and p. As the reporting does not involve more interprocessor communication than the counting, the algorithm achieves a full speedup of p for k≥ O(max(n log n log p, n log³ p)) even on a hypercube.