Technical Reports


Display by Author:
A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z
Search by for:

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: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.