CSE581: Computational Geometry

Spring 1999
Time: Mon Wed Fri, 9:00 AM to 9:50 AM
Location: 17 Norton Hall
Instructor: Ashim Garg
Registration Numbers: 199348 (Section R1), 492833 (Section R2) and 002740 (Section R3)

This course introduces students to the essentials of Computational Geometry and presents an in-depth study of the fundamental techniques used in this field. Students will not only gain a theoretical understanding of these techniques, but will also acquire practical knowledge through programming projects. Applications to problems from other fields such as Computer Graphics, Computer Vision, Software Engineering, Image Processing, Databases, and Geographical Information Systems will also be discussed.

Given below is an outline of the course. Please contact me for any further information regarding the course.

Course Outline

• Introduction
  • Overview
  • Algorithmic Background
  • Elementary Data Structures and Techniques
• Searching
  • Planar Point Location
  • Two-dimensional Range Searching
  • Multi-dimensional Range Searching
• Convex Hulls
  • Point Sets in Two Dimensions
  • Point Sets in Three Dimensions
  • Approximate Convex Hulls
• Proximity
  • The Closest-pair Problem
  • Voronoi Diagrams
  • Euclidean Minimum Spanning Trees
  • Planar Triangulations
• Intersection
  • The Hidden Line and Hidden Surface Problems
  • Line Segments
  • Rectangles
  • Convex Polygons
  • General Polygons
• Graph Drawing
  • Drawing Trees
  • Straightline Drawings
  • Orthogonal Drawings
  • Upward Drawings

Grading

Grading will be based on homeworks, projects, and exams.

Prerequisites

Basic knowledge of data structures, or instructor's permission.

Textbooks

(Required) "Computational Geometry: An Introduction", Franco P. Preparata and Michael Ian Shamos, Springer-Verlag, 1991, ISBN: 0387961313.

(Recommended) "Graph Drawing: Algorithms for Visualizing Graphs", G. Di Battista, P. Eades, R. Tamassia, and I.G. Tollis, Prentice Hall, 1998, ISBN 0133016153.

 
• About this document ...