Skip to Main content Skip to Navigation
Journal articles

Scalable algorithms for bichromatic line segment intersection problems on coarse grained multicomputers

Olivier Devillers 1 Andreas Fabri 1
1 PRISME - Geometry, Algorithms and Robotics
CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : 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^2, 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 O( (n log n log p)/p + Ts(n log p,p) ), where Ts(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 O(k/p) 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 p/log p 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 p/log^2p and p/log p 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^3 p)) even on a hypercube.
Document type :
Journal articles
Complete list of metadatas

https://hal.inria.fr/hal-00795079
Contributor : Olivier Devillers <>
Submitted on : Wednesday, February 27, 2013 - 11:30:14 AM
Last modification on : Saturday, January 27, 2018 - 1:31:39 AM

Links full text

Identifiers

Collections

Citation

Olivier Devillers, Andreas Fabri. Scalable algorithms for bichromatic line segment intersection problems on coarse grained multicomputers. International Journal of Computational Geometry and Applications, World Scientific Publishing, 1996, 6 (4), pp.487-506. ⟨10.1142/S0218195996000307⟩. ⟨hal-00795079⟩

Share

Metrics

Record views

244