234 - Advanced Computational Geometry

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

Tentative Syllabus

1.

Introduction
Why randomized and approximation alkgorithms?

2.

Approximation Algorithms and Techniques

(a)

Metric approximation

i.

Clarkson spanners (0.5-1 meeting).

ii.

[Arya, Das, Mount, Salowe, and Smid, STOC95] spanners.

iii.

Arora's algorithm (1.5-2 Meetings).

iv.

Smith and Rao approximation algorithm - sketch (0.3-0.5 meeting).

(b)

Shape approximation

i.

Warmup exercise - approximating the diameter (Andrews result). (15-20 minutes)

ii.

Approximating a convex polytope (Dudley's Method). (0.3-0.5 meeting). Approximating the diameter using Dudley method.

iii.

Approximating polytopes using Clarkson method.

iv.

Approximating the minimum volume bounding box in 3d.

(c)

Nearest neighbor queries.

(Motwani, Indyk) or (Rabani, et al), and/or Arya, Mount.

3.

Surface reconstruction.

(a)

2d - Amenta, et al. + Dey (proof Dey version?)

(b)

Gold (SoCG 99).

(c)

3d - Amenta, Bern - describe the mess.

4.

Arrangements and randomized algorithms

(a)

Motiion planning.

(b)

Incidents (lower+upper bound) in the plane.

(c)

Planarity arguements - k-set, k-level, incidences.

(d)

Application for k-sets: Matousek cuttings.

(e)

Basic Range searching: point-locations, half-space range-searching, simplex range-searching.

(f)

Clarkson-Shor.
Example: Delaunay triangulation [backward analysis].

(g)

VC-Dimension.

(h)

Exponential decay and (Chazelle Friedman Cuttings) Cuttings.

(i)

Lazy Randomized incremental construction.

5.

Lower bounds

• 3-sum hard problems.
• Chazelle lower bounds for range searching (get paper from Pankaj).

6.

Robustness

(a)

Melhorn stuff? See Stefan Schirra recent paper.

(b)

Grid snapping (paper by Guibas et al.).

(c)

Greene & Yao.