CPS234: COMPUTATIONAL GEOMETRY

Term: Spring 2004
Time: Tu Th 3:50pm - 5:05pm
Location: LSRC D243
Instructors: Herbert Edelsbrunner and Alper Üngör
featuring Yusu Wang
Http:// www.cs.duke.edu/courses/spring04/cps234
Computational geometry is the field of theoretical computer science devoted to the design, analysis, and implementation of algorithms and data structures to solve geometric problems. It has numeruous application domains including computer graphics, visualization, robotics, computational biology, data mining, parallel computing, and scientific computing. This course will survey the fundamental concepts in geometric algorithms and data structures. Topics that will be covered include

  • Convex hulls
  • Plane-sweep algorithms
  • Triangulations
  • Geometric data structures
  • Range searching
  • Point location
  • Voronoi diagrams
  • Delaunay triangulations
  • Randomized algorithms
  • Arrangements
  • Nearest neighbors
  • Surface simplification
  • Morse theory
  • Reeb graphs

    • Duke catalog number: 7764
    Units: 3
    Pre-requisites: CPS 230 or equivalent, or Instructor's permission
    Textbook (main):
  • Computational Geometry: Algorithms and Applications.
    M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf.
    Springer-Verlag, 2nd edition, 2000.
    • Textbooks (recommended):
  • Algorithms in Combinatorial Geometry. H. Edelsbrunner. Springer-Verlag, 1987.
  • Geometry and Topology for Mesh Generation. H. Edelsbrunner. Cambridge Univ. Press, 2001.
  • Computational Geometry: An Introduction Through Randomized Algorithms. K. Mulmuley. Prentice-Hall, 1994.
  • Computational Geometry: An Introduction. F. Preparata and M. Shamos, Springer-Verlag, 1985.
  • Computational Geometry in C. J. O'Rourke, Cambridge University Press, 1994.
  • We will also distribute survey and research papers from recent conferences and journals on the course web site.
    • Coursework: Grades will be based on homeworks (30%), a semester project (30%), a final exam (30%) and class participation (10%).
    Alper Üngör (ungor@cs.duke.edu) January 2004