Files: Description File size 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
PDF
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
REFERENCE TO THIS PAGE:
Fjällström, Per-Olof (1997). Batched Range Searching on a Mesh-Connected SIMD Computer in Linköping Electronic Articles in Computer and Information Science, 2(?). http://www.ep.liu.se/ea/cis/1997/007/. ()