CSE355

Course CSE355
Title Computational Geometry
Credits 3
Course Coordinator

Joseph S. B. Mitchell

Description

The design and analysis of efficient algorithms to solve geometric problems that arise in computer graphics, robotics, geographical information systems, manufacturing, and optimization. Topics include convex hulls, triangulation, Voronoi diagrams, visibility, intersection, robot motion planning, and arrangements. This course is offered as both AMS 345 and CSE 355.

Prerequisite AMS 301; programming knowledge of C or C++ or Java
Course Outcomes
  • An understanding of the fundamental algorithms and structures in computational geometry, such as convex hulls, triangulation, Voronoi diagrams, and arrangements.
  • An ability to apply geometric algorithms in computer graphics, robotics, geographical information systems, and manufacturing.
  • A working knowledge of design, analysis, and implementation of computer algorithms.

Textbook

Computational Geometry in C, Second Edition, By Joe O'Rourke, Cambridge University Press, 1998, ISBN 0-521-64976-5

Major Topics Covered in Course
  • Polygons, triangulation, visibility, art gallery problems
  • Convex hulls in two and higher dimensions
  • Proximity problems: closest pair, closest point queries
  • Voronoi diagrams, Delaunay diagrams
  • Geometric minimum spanning trees, traveling salesman problem
  • Arrangements of lines, hyperplanes; geometric duality
  • Intersection problems; Bentley-Ottmann sweep
  • Point location search

Laboratory Projects

N/A

Course Webpage

CSE355