Simplex range searching and its variants: A review
© Springer International Publishing AG 2017. 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 Rd, and let R be a family of subsets of Rd; elements of R are called ranges. Preprocess S into a data structure so that for a query range γ ε 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.
- A Journey through Discrete Mathematics: A Tribute to Jiri Matousek
Start / End Page
International Standard Book Number 13 (ISBN-13)
Digital Object Identifier (DOI)