ICS 266, Spring 1996:
Computational Geometry

Instructor: David Eppstein
Office: CS 358D, phone 824-8384
Email: eppstein@ics.uci.edu

Textbooks:

Preparata and Shamos, Computational Geometry (required)
O'Rourke, Computational Geometry in C (recommended)
See also O'Rourke's online errata and source code.

Note: on May 23 and 28 I will be away at the Symposium on Computational Geometry, so there will be no lectures on those days.

Homework:

• Homework 1, due April 16
• Homework 2, due April 30
• Homework 3, due May 14
• Homework 4, due May 30

Tentative list of topics:

• Introduction - Applications of Computational Geometry

• Representation issues

  Cartesian coordinates
  projective coordinates
  complex coordinates
  

• Geometric problems

  Arrangements, incidence problems, and levels
  Convex hulls
  "The locus method" -- Voronoi diagrams
  Data structures -- range search, range reporting, point location
  

• Problem transformation

  Projective duality
  Planar duality
  The lifting transformation and linearization
  Pluecker coordinates
  

• Basic data structures

  Segment trees
  Interval trees
  Dobkin-Kirkpatrick recursive decomposition
  Fractional cascading -- halfspace range reporting
  

• Plane sweep

  Klee's measure problem
  Arrangements of lines and curves
  Voronoi diagrams
  

• Divide and conquer

  3d convex hulls
  Output-sensitive convex hulls
  Ham sandwich trees
  Lower envelopes and single faces in arrangements
  Davenport-Schinzel sequences
  

• Incremental and randomized incremental algorithms

  Line arrangements
  Delaunay triangulation and convex hulls
  Fixed-dimension linear programming
  

• Randomized resampling

  Fixed dimension linear programming
  Polyhedron approximation and grasp planning
  Center points
  

• Dynamic programming

  Optimal triangulation
  Geometric approximation algorithms
  

• Parametric search and geometric optimization

• Derandomization and advanced data structures

Other WWW geometry resources:

• Geometry in Action, applications of computational geometry.
• U. Minn. Geometry Center computational geometry software library.
• ICS 164, undergraduate computational geometry.
• The Geometry Junkyard, geometrical fun and games.
• Other WWW geometry resources.

David Eppstein, Dept. Information & Computer Science, UC Irvine
Last update: 26 May 2006, 16:34:46 PDT