Göm menyn
Files: Description Format
Fulltext PDF (requires Acrobat Reader)
Fulltext PostScript (requires a PostScript Reader)
Author: Per-Olof Fjällström
Article title: Batched Range Searching on a Mesh-Connected SIMD Computer
Publ. type: Article
Volume: 2
Article No: 7
Language: English
Abstract [en]: Given a set of n points and hyperrectangles in a d-dimensional space, the batched range-searching problem is to determine which points each hyperrectangle contains. We present two parallel algorithms for this problem on a √(n) * √(n) mesh-connected parallel computer: one average-case efficient algorithm based on cell division, and one worst-case efficient divide-and-conquer algorithm. Besides the asymptotic analysis of their running times, we present an experimental evaluation of the algorithms.
Keywords: Parallel algorithms, mesh-connected parallel computers, range searching
Publisher: Linköping University Electronic Press
Year: 1997
Available: 1997-07-07
No. of pages: 15
Series: Linköping Electronic Articles in Computer and Information Science
ISSN: 1401-9841

Responsible for this page: Peter Berkesand
Last updated: 2017-02-21