s'authentifier
version française rss feed

inria-00074791, version 1

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

Olivier Devillers () 1, Andreas Fabri () 1

N° RR-1882 (1993)

Résumé : We present output-sensitive scalable parallel algorithms for bichromatic line segment intersection problems for the coarse grained multicomputer model. Under the assumption that n 3 p2, 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 0(F(n log n log p;p) + T,(n log p, p)), where T,(m, p) is the time used to sort m items on a p processor machine. An additional 0(F(k;p) ) time is spent on the reporting of the k intersections. As the sequential complexity is 0(n log n) and 0(k) for counting and reporting, respectively, we obtain a speedup of F(p;log p) .As a byproduct we present algorithms for the trapezoidal de composition and 1-dimensional range query reporting with the same speedup.

  • Domaine : Informatique/Autre
  • Référence interne : RR-1882
 
  • inria-00074791, version 1
  • oai:hal.inria.fr:inria-00074791
  • Contributeur : 
  • Soumis le : Mercredi 24 Mai 2006, 16:22:11
  • Dernière modification le : Vendredi 2 Mars 2007, 11:48:37
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...