Scalable algorithms for bichromatic line segment intersection problems on coarse grained multicomputers - Inria - Institut national de recherche en sciences et technologies du numérique Access content directly
Reports (Research Report) Year : 1993

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

Olivier Devillers
Andreas Fabri
  • Function : Author
  • PersonId : 833595

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 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.

Domains

Other [cs.OH]
Fichier principal
Vignette du fichier
RR-1882.pdf (185.99 Ko) Télécharger le fichier

Dates and versions

inria-00074791 , version 1 (24-05-2006)

Identifiers

  • HAL Id : inria-00074791 , version 1

Cite

Olivier Devillers, Andreas Fabri. Scalable algorithms for bichromatic line segment intersection problems on coarse grained multicomputers. [Research Report] RR-1882, INRIA. 1993. ⟨inria-00074791⟩
145 View
112 Download

Share

Gmail Facebook X LinkedIn More