PhD Course on Advanced Range Searching (Spring 2010, Q4)



This course aims to give a detailed understanding of range searching, motivations and definitions, techniques, and the important tools used in constructing data structures for range searching problems.

Learning outcomes and competences

After attending this course, participants should be familiar with an array of tools, techniques, and theorems that are used to solve range searching problems and must be able to apply them to problems of similar flavor.


The course begins with a very broad view of range searching and the myriad of the problems that can be defined within its framework. With a careful review, three fundamental query shapes are identified: simplices, halfspaces and orthogonal boxes. These three classical problems have received considerable attention in the past decades and the techniques developed to solved them have fundamentally influenced other areas of computational geometry as well.

In the course, we shall discuss some of the most important data structures developed for each query type as well as some of the known lower bound techniques. Along the way, we will prove classical results such as cutting lemma and partition theorem.

Previous exposure to computational geometry is not required. However, some basic knowledge of probability theory will be useful. Knowledge of concepts such as epsilon-nets will greatly help to appreciate some of the results.


Peyman Afshani


DI-5523 Room 129

Course plan

Week Date Time Content Literature Lecturer
15 15 April 11:00-12:30 Introduction: definitions, variants, and motivation [AE_Survey] Peyman Afshani
16 22 April 11:00-12:30 Spanning trees with low crossing number [Welzl]
17 29 April 11:00-12:30 The cutting lemma [C1,C2]
18 6 May 11:00-12:30 The partition theorem [M1]
13:30-15:00 Applications and higher dimensional arrangements [CF]
19 11 May 9:30-11:00 Random sampling, levels, and hyperplane arrangements [S1,KS1]
20 20 May 11:00-12:30 Shallow Cutting Lemma, Shallow Partition Theorem and Applications [M2,AC1]
13:30-15:00 Dynamic Data Structures [AM]
21 27 May 11:00-12:30 Orthogonal Range Searching [A,AAL,AAL2,C3,CG1,CG2]
22 3 June 10:00-12:00 Lower Bounds [C_lb1,C_lb2,C_lb3,AAL]

Hand-in exercise




4th (Spring 2010)


5 ETCS points


Course language


Compulsory programme

Homework hand-in


Based on mandatory hand-in and attendance, pass/fail