Simplex Range Searching and Its Variants: A Review

A central problem in computational geometry, range searching arises in many applications, and numerous geometric problems can be formulated in terms of range searching. A typical range-searching problem has the following form. Let S be a set of n points in ℝ d $$\mathbb{R}^{d}$$ , and let ℛ $$\mathbb{R}$$ be a family of subsets of ℝ d $$\mathbb{R}^{d}$$ ; elements of ℛ $$\mathbb{R}$$ are called ranges. Preprocess S into a data structure so that for a query range γ ∈ ℛ $$\gamma \in \mathbb{R}$$ , the points in S ∩γ can be reported or counted efficiently. Notwithstanding extensive work on range searching over the last four decades, it remains an active research area. A series of papers by Jirka Matoušek and others in the late 1980s and the early 1990s had a profound impact not only on range searching but also on computational geometry as a whole. This chapter reviews the known results and techniques, including recent developments, for simplex range searching and its variants.