Orthogonal Range Searching.

We investigate the orthogonal range searching problem in multidimensional settings. Given n points in a d-dimensional space, the problem is to preprocess the points so that we can answer axis-parallel hyperrectangular queries asking for all points inside the hyperrectangle in sublinear time. We study data structures called the kd-tree and the range tree, and learn how we can use the data structures to solve the orthogonal range searching problem.

Computational geometry seminar series link