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

Messages

• 2/2 2010: Webpage created

Objectives

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.

Contents

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.

Lecturers

Peyman Afshani

Place

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]
		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]

Hand-in exercise

TBA

Literature

• [AE_survey] P. K. Agarwal and J. Erickson, Geometric range searching and its relatives
• [Welzl] E. Welzl, On spanning trees with low crossing numbers
• [C1] B. Chazelle, Cuttings
• [C2] B. Chazelle, Cutting hyperplanes for divide-and-conquer
• [C3] B. Chazelle, Filtering Search: A New Approach to Query-Answering
• [CG1] B. Chazelle, L.J. Guibas Fractional Cascading: I. A Data Structuring Technique
• [CG2] B. Chazelle, L.J. Guibas Fractional Cascading: II. Applications
• [CF] B. Chazelle and J. Friedman, A Deterministic View of Random Sampling and Its Use in Geometry
• [M1] J. Matousek, Efficient partition trees
• [S1] R. Seidel, The upper bound theorem for polytopes: an easy proof of its asymptotic version
• [KS1] K. L. Clarkson and P. W. Shor, Applications of random sampling in computational geometry, II
• [M2] J. Matousek, Reporting points in halfspaces
• [AC1] P. Afshani and T. M. Chan, Optimal halfspace range reporting in three dimensions
• [C_lb1] B. Chazelle, Lower Bounds for Orthogonal Range Searching: I. The Reporting Case
• [C_lb2] B. Chazelle, Lower Bounds for Orthogonal Range Searching: II. The Arithmetic Model
• [C_lb3] B. Chazelle, Lower Bounds on the Complexity of Polytope Range Searching
• [AAL] P. Afshani, L. Arge, and K. D. Larsen Orthogonal Range Reporting: Query Lower Bounds, Optimal Structures in 3-d, and Higher Dimensional Improvements
• [AAL2] P. Afshani, L. Arge, and K. D. Larsen Orthogonal Range Reporting in Three and Higher Dimensions
• [A] P. Afshani, On dominance reporting in 3D
• [AM] P. Agarwal and J. Matousek, Dynamic half-space range reporting and its applications

Quarter

4th (Spring 2010)

Credits

5 ETCS points

Prerequisites

• Algorithms and Data Structure 1
• Algorithms and Data Structure 2

Course language

English

Compulsory programme

Homework hand-in

Evaluation

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