HTML>

Syllabus: Computational Geometry F06


COMPUTATIONAL GEOMETRY 15:852 Fall 2006

INSTRUCTOR: Gary Miller
TIME: Monday Wednesday 1:30-3:00
ROOM: Wean 4623

Description:

The course text will be Computational Geometry Algorithms and Applications, 2nd ed., by de Berg, van Kreveld, Overmars, and Schwarzkopf (Springer-Verlag, 2000). We will cover most of the book, adding some additional material.

Evaluation:

Generating class lecture notes. Course work will consist of biweekly homeworks and a take-home final exam. Group work on homeworks is permitted; each student should turn in his or her own copy of the homeworks.

Tentative Topics:

  • Geometric primitives [Chap. 1]
  • Line intersection [Chaps. 2] plus randomized incremental
  • Triangulation and visibility and [Chaps. 3,15]
  • Linear programming in two and three dimensions [Chap. 4]
  • Orthogonal range searching [Chaps. 5,10]
  • Point location and Binary Space Partitions [Chaps. 6,12]
  • Voronoi diagrams and Delaunay triangulation [Chaps. 7,9]
  • Convex hulls [Chap. 11]
  • Non-orthogonal range searching [Chap. 16]

New Topics

  • Curved Elements (Bezier,B-Splines)
  • Curve Reconstruction (reconstruction a curve(surface) from sample points)
  • 3-Dimensional Geometry

Schedule:

Backwards Analysis and 2D linear Programming
  Lecture   Topic   Scribe
  September 11   Geometric primitives
  September 13   Line intersection using Sweep Line
  September 18   No Class "Meshing Roundtable"  
  September 20   No Class "Meshing Roundtable"
  September 25   Using Permutations for Topological Information Brisson CMU
  September 27   Triangulating a Polygon using Line Sweep: Read BKOS Chap 3  
  October 2   2D/3D-Linear Programming Smallest Enclosing Disc (Chap 4)  
  October 4   Trapizodial Decomposition
  October 11  
  October 16   Trapizodial Maps and tails Est.  
  October 18   Seidel's Triangulating a Polygon  
  October 23   2D convex hull: Output-sensitive and Random Incremental  
  October 25   Geometric Transforms  
  October 30   Delaunay Triangulation Min-Max angle Thm  
  November 1   3D Convex Hull  
  November 6   2D Incremental Delaunay  
  November 8   Mesh Generation--Quadtree
  November 13  
  November 15   Delaunay Refinement
  November 20   Delaunay Refinement
  November 22   Thanksgiving Holiday
  November 27   Bezier Curves and de Casteljau Algorithm 3 , 4 , 5
  November 29   B-splines
  December 4   Subdivsion Surfaces Farin Chap 21
  December 6   Convexifying Polygonal Cycles
  December 11   Convexifying Polygonal Cycles
  December 13   Surface Reconstruction

Handouts


glmiller@cs.cmu.edu