Home Bookmarks Papers Blog

234 - Advanced Computational Geometry


In this course we will dicuss topics in Computational Geometry with emphasize on randomized algorithms and approximation algorithms.

The standard computational-geometry course is not a prerequisite, and no previous knowledge in computational geometry is assumed.


Tentative Syllabus


Lectures

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.

Exercises

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

Last modified: Tue Apr 18 11:27:09 EDT 2000