Dear learners, we are now starting the last week of our computational geometry course, and it will be devoted to an important class of computational geometry problems known under the common name of Orthogonal Range Search. Let us start by providing certain motivations for solving this kind of problems. Suppose we have a database of managers of some enterprise and we would like to find those who were born between 1980 and 1990, and lead a group of four to eight people. Consequently, a manager can be now represented by a point in two-dimensional space. One axis will correspond to the date of birth, and the other one to the group size. If so, the persons we would like to find will be represented by points that fall inside an axis parallel rectangle, like the one you see now on the slide. Consequently, our question becomes an orthogonal range query. If we now impose an additional requirement, for example, a one on the salary of a manager, say we would like it to be between 3,000 to 4,000 euro. This will contribute yet another dimension to our work space. In this case, it becomes three-dimensional, and this is illustrated in the figure you see on the left. Our range query will now be a parallel [inaudible] in this three-dimensional space. Of course, we might add other requirements or restrictions. In general, an orthogonal range query will be a d-dimensional box, which is axis-parallel and results in d-dimensional space. There is a certain point behind our reasoning which might have escaped your attention. As a matter of fact, a date of birth is not a single value. It is rather a triple consisting of the date, month, and year. To be able to efficiently process orthogonal range queries, we should transform it to a single number, and it is easy to accomplish. We propose the following way for transforming a date of birth into an integer. Let us take the year and multiply it by 10,000, then take the month and multiply it by 100, and then take the date. Consequently, let us sum up these three values. Here's an example, July 16 2017, will thereby become 20,170,716, and the appropriate query interval for the date of birth between 1980 and 1990 can be chosen. For example, is 19,800,000 and 19,909,999. Now, we are ready to propose a formal statement for the orthogonal range search problem. Let us first do it for the two-dimensional case. Let P be the set of n points in the plane, and let B be a query axis-parallel rectangle. Our question is, which points from P lie inside the rectangle B? In the example you now see on the left of this slide, the respective subset of this point set P will consist of the six points, now highlighted in blue.