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