Computational Geometry (original) (raw)

CS 274 Computational Geometry Jonathan ShewchukSpring 2003Tuesdays and Thursdays, 3:30-5:00 pmBeginning January 21405 Soda Hall Synopsis: Constructive problems in computational geometry: convex hulls, triangulations, Voronoi diagrams, Delaunay triangulations, arrangements of lines and hyperplanes, subdivisions. Relationships among these problems.Techniques in computational geometry: data structures, incremental construction, divide-and-conquer algorithms, randomized algorithms, backward analysis, geometric robustness. Line segment intersection, planar subdivisions, spatial search trees, visibility graphs, small-dimensional linear programming.Applications: Nearest neighbor search; triangulation for graphics, interpolation, and terrain modeling; database queries, point locations queries, and windowing queries; collision detection; discrepancy and sampling in ray tracing; robot motion planning; cartography; art gallery theorems.

Here is Homework 1,Homework 2,Homework 3,Homework 4, andHomework 5.

The best related sites:

• David Eppstein's Geometry in Action and Geometry Junkyard.
• Jeff Erickson'sComputational Geometry Pages.
• Lists of open problems in computational geometry fromJeff Erickson,David Eppstein, andErik Demaine et al. Resources for dealing with robustness problems(in increasing order of difficulty):
• My robust predicates page (floating-point inputs, C).
• Chee Yap's CORE Library (C/C++).
• David Bailey's extensive MPFUNarbitrary precision arithmetic package (floating-point, Fortran). Look for mpfun.tex and mpfun.f.
• Olivier Devillers' predicates (integer inputs).
• Stefan N�her et al.'sLEDA contains several arbitrary precision numerical types, including integers and floating-point (C++).

Textbook

Mark de Berg,Marc van Kreveld,Mark Overmars, andOtfried Schwarzkopf(presently known as Otfried Cheong), Computational Geometry: Algorithms and Applications, second revised edition, Springer-Verlag, 2000. ISBN # 3-540-65620-0.
Known throughout the community as the Dutch Book.

Lectures

Homeworks will be irregularly assigned, and are due at the start of class on a Thursday. Homeworks are to be done alone, without help from or discussion with other humans or comparable intelligences.

For January 21, here areJeff Erickson's lecture notes on two-dimensional convex hulls.

Chew's linear-time algorithm for Delaunay triangulation of convex polygons (February 18), Seidel's linear programming algorithm (February 25 & March 4), and the Clarkson-Shor convex hull construction algorithm (April 3) are reported inRaimund Seidel, Backwards Analysis of Randomized Geometric Algorithms, Technical Report TR-92-014, International Computer Science Institute, University of California at Berkeley, February 1992. Warning: online paper is missing the figures. I'll hand out a version with figures in class.

For March 4, I will hand out the appendix from Raimund Seidel's_Small-Dimensional Linear Programming and Convex Hulls Made Easy_, Discrete & Computational Geometry 6(5):423-434, 1991. For anyone who wants to implement the linear programming algorithm, this appendix is a better guide than the Dutch Book. Unfortunately, there is no online version.

For April 1, I will hand out Raimund Seidel's_The Upper Bound Theorem for Polytopes: An Easy Proof of Its Asymptotic Version_, Computational Geometry: Theory and Applications 5:115-116, 1985. Don't skip the abstract: the main theorem and its proof are both given in their entirety in the abstract, and are not reprised in the body at all. Unfortunately, there is no online version.

For April 24, here is theBSP FAQ.

For May 6, here areSamir Khuller's notes on visibility graphs.

For May 8, here are myLecture Notes on Geometric Robustness.

For the Project, read Leonidas J. Guibas and Jorge Stolfi,Primitives for the Manipulation of General Subdivisions and the Computation of Voronoi Diagrams, ACM Transactions on Graphics 4(2):74-123, April 1985. Unfortunately, there is no online version, but I'll hand it out in class. Feel free to skip Section 3, but read the rest of the paper. See also this list of errors in the Guibas and Stolfi paper, and Paul Heckbert, Very Brief Note on Point Location in Triangulations, December 1994. (The problem Paul points out can't happen in a Delaunay triangulation, but it's a warning in case you're ever tempted to use the Guibas and Stolfi walking-search subroutine in a non-Delaunay triangulation.)

Geometry Applets

These applets can be quite helpful in establishing your geometric intuition for several basic geometric structures and concepts.

• Convex hulls
• Delaunay triangulations
• Voronoi diagrams and Delaunay triangulations I
• Voronoi diagrams and Delaunay triangulations II
• The duality of points and lines in the plane
• Line sweep
• The art gallery problem
• Fortune's sweep-line Delaunay triangulation algorithm
• Quadtrees of points in the plane

Prerequisites

• CS 170 (Advanced Algorithms) or the equivalent.
• A basic course in probability.

Grading

• 80% for the homeworks.
• 20% for the project: a Delaunay triangulation implementation, or an alternative by arrangement with the instructor.

Supported in part by the National Science Foundation under Awards ACI-9875170, CMS-9980063, CCR-0204377, and EIA-9802069, and in part by a gift from the Okawa Foundation.