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.
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.
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.
http://jeffe.cs.illinois.edu/pubs/survey.html
T. M. Chan.
Persistent Predecessor Search and Orthogonal Point Location on the Word RAM.
Manuscript, 2010.
https://cs.uwaterloo.ca/~tmchan/veb_7_10.ps
J. Matou\v{s}ek.
Efficient Partition Trees.
Discrete and Computational Geometry, 8:315-334, 1992.
http://link.springer.com/10.1007%2FBF02293051?LI=true&from=SL
T. M. Chan.
Optimal Partition Trees.
In Proc. 26th ACM Sympos. Comput. Geom., pages 1-10, 2010.
https://cs.uwaterloo.ca/~tmchan/optpt_2_10.pdf
Applications of a Planar Separator Theorem
Richard J. Lipton and Robert E. Tarjan
Technical Report, Stanford university, Stan-CS-77-628, October 1977
ftp://reports.stanford.edu/pub/cstr/reports/cs/tr/77/628/CS-TR-77-628.pdf
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: http://cglab.ca/~morin/publications/ds/entropy-submitted.pdf
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
http://www.computer.org/csdl/proceedings/focs/1990/2082/00/089528-abs.html
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
http://dl.acm.org/citation.cfm?id=1240240
Expected asymptotically optimal planar point location
John Iacono
Computational Geometry, Volume 29, Issue 1, September 2004, Pages 19-22
http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6TYS-4CDHJS0-1&_user=642076&_coverDate=09%2F30%2F2004&_rdoc=1&_fmt=high&_orig=search&_sort=d&_docanchor=&view=c&_searchStrId=1435307638&_rerunOrigin=google&_acct=C000034578&_version=1&_urlVersion=0&_userid=642076&md5=bf7a6beb06818954a2325d8db17c2b91
Optimal Search in Planar Subdivisions
David G. Kirkpatrick
SIAM Journal of Computing, Columne 12, Nubmer 1, February 1983, pages 28-35
http://siamdl.aip.org/getpdf/servlet/GetPDFServlet?filetype=pdf&id=SMJCAT000012000001000028000001&idtype=cvips
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
http://portal.acm.org/ft_gateway.cfm?id=6151&type=pdf&coll=GUIDE&dl=GUIDE&CFID=98635603&CFTOKEN=35102846
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
http://www.computer.org/csdl/proceedings/focs/1977/5428/00/542800162-abs.html
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
http://siamdl.aip.org/getpdf/servlet/GetPDFServlet?filetype=pdf&id=SMJMAP000036000002000177000001&idtype=cvips
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
http://link.springer.de/link/service/series/0558/papers/2461/24610152.pdf