@TECHREPORT{R-96-27,
NUMBER = {R-96-27},
INSTITUTION = ida,
ADDRESS = idaaddr,
YEAR = {1996},
AUTHOR = {Fj{\"a}llstr{\"o}m, Per-Olof},
TITLE = {Range Searching on a Mesh-Connected Parallel Computer
},
ABSTRACTURL = {/publications/cgi-bin/tr-fetch.pl?r-96-27+abstr},
ABSTRACT = {Given a set of n points and hyperrectangles in d-dimensional space, the range-searching problem is to determine which points each hype rectangle contains. We present two parallel algorithms for this problem on a mesh-connected parallel computer: one average case efficient algorithm based on cell division, and one worst-case efficient divide-and-conquer algorithm. In addition to the asymptotic analysis of their running times, we present an experimental evaluation of the algorithms.
}