CIS 677: Computational Geometry

Instructor Name: Ken Clarkson Phone: 908 582 4717 E-mail:clarkson@bell-labs.com Office, and hours: from 11-12 before class, Prof. Sampath Kannan's office. after class, the theory lab. Class Time: Mondays, Noon-3 Location: Towne 321 Prerequisite CIS 502 or equivalent Grading Four homework assignments (roughly) One term paper or programming project; suggestions

Textbook

Reference Books

• K. Mulmuley, Computational Geometry: An Introduction Through Randomized Algorithms, Prentice Hall, Englewood Cliffs, NJ, 1994.
• F. P. Preparata and M. I. Shamos, Computational Geometry: An Introduction (Second edition), Springer-Verlag, New York, 1988.
• H. Edelsbrunner, Algorithms in Combinatorial Geometry, Springer--Verlag, Heidelberg, 1987.
• J O'Rourke. Computational Geometry in C.
• D-Z Du and F. Hwang, Ed.s. Computing in Euclidean Geometry.
• K. Mehlhorn, Data Structures and Algorithms 3: Multi-dimensional Searching and Computational Geometry, Springer--Verlag, Heidelberg, 1984.

Lectures and homework

Course Synopsis

An introduction via planar convex hulls

• basic facts about convexity
• Jarvis march, Graham scan and its variants
• approximate arithmetic
• randomized incremental algorithm
• combinatorial geometry: <=k-sets

Coordinate-wise dominance, orthogonal range queries

• interval trees, segment trees, filtering search, priority search trees.
• algorithms: divide-and-conquer, fast dominance

Planar subdivisions

• point-in-polygon testing, area of polygons
• line segment intersection, trapezoidal diagrams, output sensitivity
• sweepline algorithm
• randomized algorithms: polygon triangulations, general case

Planar point location

• algorithms: walking through subdivisions, bucketing, Seidel, Kirkpatrick
• representing planar subdivisions

Voronoi diagrams, Delaunay triangulations, convex polytopes

• algorithms: sweepline, divide-and-conquer
• alpha-shapes
• regular triangulations, convex dependencies
• Delaunay triangulations as convex hulls
• Caratheodory's theorem, locus approach, duality, halfspace intersection, arrangements
• algorithms: beneath/beyond, offline randomized, semi-dynamic, *fully dynamic
• output-sensitivity
• implementing primitives: *polytope volume, *alpha-shape testing
• *convex hulls in really high dimension

Low-dimensional linear programming and optimization

• algorithms: recursive, iterative reweighting, Seidel's, subexponential simplex
• smallest enclosing sphere, convex programming, LP-type problems

*Helly properties

• Radon's theorem, Helly's theorem, centerpoints
• epsilon nets and discrepency

Simplex range searching, VC dimension

Geometric search trees

• quad-trees: all-nearest-neighbors, n-body simulation, mesh generation
• kd-trees (also known as CART, structured codebooks...): neighbor searching, classification
• binary space partition trees

Geometric graph problems

• minimum spanning trees, narrow cones
• shortest paths, spanners, and visibility
• matching
• traveling salesman

Degeneracy and robustness

• perturbations and their avoidance
• filtering
• fast exact arithmetic