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.
Type de document :
Article dans une revue
International Journal of Computational Geometry and Applications, World Scientific Publishing, 1996, 6 (4), pp.487-506. 〈10.1142/S0218195996000307〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00795079
Contributeur : Olivier Devillers <>
Soumis le : mercredi 27 février 2013 - 11:30:14
Dernière modification le : jeudi 11 janvier 2018 - 16:56:52

Identifiants

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〉

Partager

Métriques

Consultations de la notice

152