Quasi-Optimal Upper Bounds for Simplex Range Searching and New Zone Theorems

Report ID: TR-290-90

---

Author: Chazelle, Bernard / Sharir, Micha / Welzl, Emo

---

Date: 1990-10-00

---

Pages: 23

---

Download Formats: |PDF|

---

Abstract:

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 0. To fine tune our results in the reporting case we also establish new zone theorems for arrangements and merged arrangements of planes in 3-space, which are of independent interest.