|
TR-290-90
Quasi-Optimal Upper Bounds for Simplex Range Searching and New Zone Theorems |
|
| Authors: | Chazelle, Bernard, Sharir, Micha, Welzl, Emo |
| Date: | October 1990 |
| Pages: | 22 |
| Download Formats: | |
This paper presents quasi-optimal upper bounds for simplex range searching. The problem is to preprocess a set P of n points in Rd so that, given any query simplex q, the points in P intersect q can be counted or reported efficiently. If m units of storage are available (n |
|