The standard computational-geometry course is not a prerequisite, and no previous knowledge in computational geometry is assumed.
|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|
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|
|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|
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.|
[Linear programming should be LP-type in the enclosing disk question]