Home | Bookmarks | Papers | Blog |
The standard computational-geometry course is not a prerequisite, and no previous knowledge in computational geometry is assumed.
1. | 14/1/2000 | Introduction |
2. | 19/1/2000 | Diameter - Approximation Algorithms (ppt, sdd) |
3. | 24/1/2000 | Quadtrees and its applications |
4. | 31/1/2000 | Well Separated Pairs Decomposition |
5. | 2/2/2000 | Well Separated Pairs Decomposition - applications |
6. | 2/7/2000 | Approximate Nearest
neighbor Searching in Fixed Dimensions
The paper of Arya et al. the talk is based on. |
7. | 2/9/2000 | Approximate Nearest neighbor Searching in Fixed Dimensions continued |
8. | 2/14/2000 | Approximating a convex shape using Dudley Method |
9. | 2/16/2000 | Approximate Traveling Salesman |
10. | 2/21/2000 | Approximate Traveling Salesman - continued |
11. | 2/23/2000 | Approximate Traveling Salesman - proof |
12. | 2/28/2000 | On geometric primitives and linear programming in the plane. |
13. | 3/1/2000 | On incidences between lines and points |
15. | 3/20/2000 | Randomized incramental algorithms - Clarkson/Shor. Based on this (later) paper. |
16. | 3/22/2000 | Exponential decay lemma (see this paper) |
17. | 3/27/2000 | Clarkson-Shor, at most k-level |
18. | 3/29/2000 | Cuttings. |
19. | 4/3/2000 | The complexity of k-level, matousek cuttings. |
20. | 4/5/2000 | Linear programming and LP-type problems A subexponential bound of linear programming, Matousek, Sharir, Welzl, 1992. |
21. | 4/10/2000 | Spanning tree with low crossing numbers Based on a result due to Emo Welzl, which you get here. |
22. | 4/12/2000 | Davenport Schinzel Sequences, lower envelopes, and the inverse of the Ackerman function |
23. | 4/17/2000 | Partition trees Proceedings version Efficit Paritition Trees, J, Matousek. Efficient Partition Trees, J. Matousek in Discrete and Computational Geometry 8(1992), 315-334. |
24. | 4/18/2000 | Partition Trees continued.- Last and final meeting. |
1. | 2/21/2000 | Exercise 1 |
2. | 3/22/2000 |
Exercise 2 [Linear programming should be LP-type in the enclosing disk question] |
3. | 5/1/2000 | Exercise 3 |