Old Well

Department of Computer Science
College of Arts and Sciences
The University of North Carolina at Chapel Hill

COMP290-72: Computational Geometry and Applications


Instructor: Ming C. Lin
Time and place:TR 2:00pm - 3:15pm, SN 325
Prerequisites: An advanced undergrad course in algorithms (COMP122 or equivalent)
Textbook: Computational Geometry (Algorithms and Applications), by de Berg, van Kreveld, Overmars and Schwarzkofp, Springer-Verlag, 1997 (377 pages; ISBN#3-540-61270-X).

  • Course Overview
  • Lectures and Approximate Schedule
  • Assignments and Projects
  • Geometric Algorithms & Software Available on the Web
  • More Pointers to the Web
  • Additional Reference Materials
  • Class Roster

  • Course Overview:

    The goal of the class is to get an appreciation of geometric algorithms, to understand the various considerations and tradeoffs used in designing geometric algorithms (e.g. time, space, robustness, and generality) for various applications. We will cover some basic geometric data structures and algorithms, their complexity, implementation and applications. Topics to be covered will vary depending on the interests of students and possible guest lectures. The preliminary topic list includes:
  • Proximity and Intersection
  • Voronoi Diagrams and Delaunay Triangulation
  • Linear Programming in Lower Dimension
  • Geometric Search
  • Arrangements of Hyperplanes
  • Convex Hulls, Polytopes and Computation
  • Numerical Robustness
  • Randomized Algorithms
  • The lectures will also focus on the applications of geometric algorithms and data structures in the following areas:
  • Computer Graphics
  • Geometric Modeling
  • Robot Motion Planning
  • Scientific Computing
  • Vision and Imaging
  • Each topic will be motivated by an interesting example, then studied in couple lectures about its basic concepts and followed by applications. Each student will also be expected to give a presentation on one of these topics or other topics on geometric computing under the instructor's guidance.

    Lectures and Approximate Schedule

    Here is a list of TENTATIVE lecture topics (subject to changes). Schedule and information on each topic (e.g. readings, web pointers) will be added during the semester before each class.

  • Introduction (Aug 18, 1998)
  • Line Segment Intersection (Aug 20, 1998)
  • Line Segment Intersection: App in 3D Polyhedral Morphing (Aug 25, 1998)
  • Polygon Triangulation (Aug 27, 1998)
  • Robustness Issues (September 1, 1998)
  • Polygon Triangulation: Implementation & Apps (September 3, 1998)
  • Linear Programming (September 8, 1998)
  • Linear Programming (September 10, 1998)
  • Orthogonal Range Searching (September 15, 1998)
  • Orthogonal Range Searching: App in Crystal Structure Determination (September 17, 1998)
  • Point Location (September 22, 1998)
  • Polygonization of Implicit Surfaces (September 24, 1998)
  • Voronoi Diagram (September 29, 1998)
  • Geometric Problems in Cloth Simulation (October 1, 1998)
  • Arrangements & Duality (October 6, 1998)
  • Survey on Subdivision Surfaces (October 8, 1998)
  • Project Proposal - Part I (October 13, 1998)
  • Fall Break (October 15, 1998)
  • Project Proposal - Part II (October 20, 1998)
  • Constructing Voronoi Diagram (October 22, 1998)
  • Delaunay Triangulations (October 27, 1998)
  • Delaunay Triangulations: Applications (October 29, 1998)
  • Geometric Data Structures (November 3, 1998)
  • Geometric Search: App in Query Image Databases (November 5, 1998)
  • Convex Hulls (November 10, 1998)
  • Model Simplification (November 12, 1998)
  • Project Update (November 17, 1998)
  • Robot Motion Planning (November 19, 1998)
  • Minkowski Sum and Distance Computation (November 24, 1998)
  • Thanksgiving (Nov 26, 1998)
  • Visibility Computation (December 1, 1998)
  • Comprehensive Reviews & Future Directions (December 3, 1998)

  • Assignments and Projects

    The class grade of each student is determined by
  • Homework (30%)
  • Class Presentation (20%)
  • Final Project (50%)

  • Geometric Algorithms and Softwares Available on the Web:

    Here are just some possible locations to find geometric software/libraries and algorithmic toolkits you may need:
  • A comprehensive collection of geometric software
  • CGAL: Computational Geometry Algorithms Library (in C++)
  • LEDA: Library of Efficient Datatypes and Algorithms (in C++)
  • The Stony Brook Algorithm Repository: Implementation in C, C++, Pascal and Fortran
  • CMU's Computer Vision Homepage
  • Finite element mesh generation and More
  • VLSI routing problems
  • Computational gene recognition (a bibliography)
  • Machine learning resources

  • More Pointers to the Web on Geometry:

    Here are some good starting points to navigate among the webs of the Web......
  • Jeff Erickson's Computational Geometry Page: Wonderful collection of web pointers.
  • David Eppstein's Geometry in Action: Applications of computational geometry.
  • The Carleton Computational Geometry Resources: Another excellent collection of resources.
  • Toussant's Geometric Link to many other sites, including those on animation of geometric algorithms.

  • Additional Reference Materials

    Other reference books:

  • Computational Geometry In C (Second Edition), by O'Rourke, Cambridge University Press, 1998.
  • Handbook on Discrete and Computational Geometry, by Goodman and O'Rourke (eds), CRC Press LLC, 1997.
  • Applied Computational Geometry: Toward Geometric Engineering, by Lin and Manocha (eds), Springer-Verlag, 1996.
  • Computational Geometry: An Introduction Through Randomized Algorithms, by Mulmuley, Prentice Hall, 1994.
  • Robot Motion Planning, by Latombe, Kluwer Academic Publishers, 1991.
  • Algorithms in Combinatorial Geometry, by Edelsbrunner, Springer-Verlag, 1987.
  • Computational Geometry (An Introduction), by Preparata and Shamos, Springer-Verlag, 1985.

  • Other reference papers used in lectures:

    * Delaunay Triangulation and Applications *

  • Delaunay Triangulation Applets by Paul Chew
  • Constraint Delaunay Triangulation by Jonathan Shewchuk
  • A Delaunay Refinement Algorithm for Quality 2-D Mesh Generation by J. Ruppert, J. Algorithms, pp. 548-585, May 1995
  • "Cubic Spline Fitting using data dependent triangulations" by E. Quak, L. Schumaker et al., Computer Aided Geometric Design, 7(1990), p293-301.
  • "Minimal roughness property of Delaunay Triangulation", by S. Rippa, Computer Aided Geometric Design, 7(1990), p489-497.
  • Special Issue on Computational Geometry and Computer Graphics, IEEE Proceedings, ed. by D. Dobkin, Vol.80, No.9, 1992.
  • * Query Image Database *
  • Research at Stanford Vision Laboratory
  • Image Metrics using the Hausdorff Distance

  • For more information, contact Ming C. Lin, lin@cs.unc.edu.

    Copyright 1998. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the author.

    This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.