# A Journey Through Discrete MathematicsSimplex Range Searching and Its Variants: A Review

A Journey Through Discrete Mathematics: 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\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$\mathbb{R}^{d}$$ \end{document}, and let ℛ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$\mathbb{R}$$ \end{document} be a family of subsets of ℝd\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$\mathbb{R}^{d}$$ \end{document}; elements of ℛ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$\mathbb{R}$$ \end{document} are called ranges. Preprocess S into a data structure so that for a query range γ∈ℛ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$\gamma \in \mathbb{R}$$ \end{document}, 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.] http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png

# A Journey Through Discrete MathematicsSimplex Range Searching and Its Variants: A Review

Editors: Loebl, Martin; Nešetřil, Jaroslav; Thomas, Robin
Springer Journals — May 9, 2017
29 pages

/lp/springer-journals/a-journey-through-discrete-mathematics-simplex-range-searching-and-its-CIwjwqOLAM
Publisher
Springer International Publishing
© Springer International publishing AG 2017
ISBN
978-3-319-44478-9
Pages
1 –30
DOI
10.1007/978-3-319-44479-6_1
Publisher site
See Chapter on Publisher Site

### Abstract

[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\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$\mathbb{R}^{d}$$ \end{document}, and let ℛ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$\mathbb{R}$$ \end{document} be a family of subsets of ℝd\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$\mathbb{R}^{d}$$ \end{document}; elements of ℛ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$\mathbb{R}$$ \end{document} are called ranges. Preprocess S into a data structure so that for a query range γ∈ℛ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$\gamma \in \mathbb{R}$$ \end{document}, 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.]

Published: May 9, 2017

Keywords: Simplex Range Searching; Range Counting Queries; Linear Size Data Structure; Query Time; Query Halfspace