Course material

Course material

Handouts, notes from lectures etc. will be accessible from this web page as they are produced by the lecturers at the school.

Note that the below listed material (except background literature) will be given to all participants as printed versions at the school.


1: Data-Structures for Geometric Approximation by Sariel Har-Peled

2: Orthogonal Range Queries, Basic Methods by Timothy Chan

3: A Taxonomy of Range Queries, Mihai Pătraşcu

4: Orthogonal Range Queries, Mihai Pătraşcu

5: Lower Bounds for Predecessor Search, Mihai Pătraşcu

6: Ω(lgn/lglgn) Lower Bounds, Mihai Pătraşcu

7: TSP, Sariel Har-Peled.

Lecture notes

1: Har-Paled notes Tuesday

2: Point location - using the planar, John Iacono

3: Point location - using persisance, John Iacono

4: Kirkpatrick's, John Iacono

5: Sariel Har-Peled, Wednesday.

6: Sariel Har-Peled, Thursday morning.

7: John Iacono, Thursday morning.

8: Sariel Har-Peled notes Thursday afternoon.

9: John Iacono, Thursday afternoon.

List of background literature

Below is listed literature relevant to the MADALGO Summer School on Geometric data Structures (more will be added).


P. K. Agarwal and J. Erickson.
Geometric Range Searching and Its Relatives.
In "Discrete and Computational Geometry: Ten Years Later"
(B. Chazelle, J. E. Goodman, and R. Pollack, eds.), AMS Press, pages 1-56, 1999.

T. M. Chan.
Persistent Predecessor Search and Orthogonal Point Location on the Word RAM.
Manuscript, 2010.

J. Matou\v{s}ek.
Efficient Partition Trees.
Discrete and Computational Geometry, 8:315-334, 1992.

T. M. Chan.
Optimal Partition Trees.
In Proc. 26th ACM Sympos. Comput. Geom., pages 1-10, 2010.

Applications of a Planar Separator Theorem
Richard J. Lipton and Robert E. Tarjan
Technical Report, Stanford university, Stan-CS-77-628, October 1977

Distribution-Sensitive Point Location in Convex Subdivisions
Sébastien Collette, Vida Dujmović, John Iacono, Stefan Langerman, Pat Morin 
Proceedings of the 19th ACM-SIAM Symposium on Discrete Algorithms (SODA 2008), pages 912-921, 2008. 
Full version:

New results on dynamic planar point location
S.W. Cheng, R. Janardan
Proceedings of the 31st Annual IEEE Symposium on Foundations of Computer Science (FOCS 1990), 1990, pp. 96-105

A Simple Entropy-Based Algorithm for Planar Point Location
Sunil Arya, Theocharis Malamatos, David M. Mount
ACM Transactions on Algorithms, Vol. 3, No. 2, Article 17, 2007

Expected asymptotically optimal planar point location 
John Iacono
Computational Geometry, Volume 29, Issue 1, September 2004, Pages 19-22

Optimal Search in Planar Subdivisions
David G. Kirkpatrick
SIAM Journal of Computing, Columne 12, Nubmer 1, February 1983, pages 28-35

Planar Point Location Using Persistent Search Trees
Neil Sarnak, Robert E. Tarjan
Communications of the ACM, Volumne 29, Nubmer 7, July 1986, pages 669-679

Applications of a Planar Separator Theorem
Richard J. Lipton, Robert Endre Tarjan
Proceedings of the 18th Annual Symposium on Foundations of Computer Science (FOCS 1977), pages 162-170, 1977

A Separator Theorem for Planar Graphs
Richard J. Lipton, Robert Endre Tarjan
SIAM Journal of Applied Mathematics, Volume 6, Number 2, April 1979, pages 177-189

Two Simplified Algorithms for Maintaining Order in a List
Michael A. Bender, Richard Cole, Erik D. Demaine, Martin Farach-Colton, and Jack Zito
Proceedings of the 10th Annual European Symposium on Algorithms (ESA 2002), Lecture Notes in Computer Science, volume 2461, September 17–21, 2002, pages 152–164