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.
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.
DI-5523 Room 129
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] | |
13:30-15:00 | |||||
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] | |
13:30-15:00 | |||||
22 | 3 June | 10:00-12:00 | Lower Bounds | [C_lb1,C_lb2,C_lb3,AAL] |
TBA
4th (Spring 2010)
5 ETCS points
English
Homework hand-in
Based on mandatory hand-in and attendance, pass/fail