| 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/.
() |
|