Simplex range searching and its variants: A review

Published

Book Section

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

Full Text

Duke Authors

Cited Authors

  • Agarwal, PK

Published Date

  • January 1, 2017

Book Title

  • A Journey through Discrete Mathematics: A Tribute to Jiri Matousek

Start / End Page

  • 1 - 30

International Standard Book Number 13 (ISBN-13)

  • 9783319444789

Digital Object Identifier (DOI)

  • 10.1007/978-3-319-44479-6_1

Citation Source

  • Scopus