CS583 - Computational Geometry

 

 

  F a l l 2 0 0 7 

 

 

Instructor

Prof. Shawn Shamsian
Email: sshamsia(at)usc(dot)edu
Lecture: Friday, 2:00~5:00pm
Office hours: Monday, 2:00~3:00pm; Friday, 1:00~2:00pm (and by appointment)
Office location: SAL 236
 

Textbook (required)

  • Computational Geometry: Algorithms and Applications.
    M de Berg, M. van Kreveld, M. Overmars and O. Schwarzkopf.
    Second edition.
    Springer Verlag
 

Prerequesite

  • CS 303 "Design and Analysis of Algorithms"
  • Good programming skills. Ability to convert informal descriptions into computer algorithms. Students must be able to program in C++.
 

Course Objective

The objective of this course is to provide basic and advanced study of algorithms and data structures that are particularly suitable for solving problems of geometric nature. The course will introduce basic tools and algorithms and address fundamental problems such as convex hulls, polygon triangulation, range search, Voronoi diagrams, Delaunay triangulations...
Theoretical aspects will be covered during the lectures. Homework and programming assignments will cover some extensions and provide some hands-on experience.

 

Course Requirement

There will be two exams:

  • Exam I on October 5th, 2007.
  • Exam II on November 16th, 2007.

Each exam will count for 30% of the course grade. The rest of the grade will be determined by programming assignments (30%) and paper presentations (10%).

 

Academic Integrity

The USC Student Conduct Code prohibits plagiarism. All USC students are responsible for reading and following the Student Conduct Code, which appears on pp. 83-97 of the 1997-1998 SCampus.

In this course we encourage students to study together. This includes discussing general strategies to be used on individual assignments. However, all work submitted for the class is to be done individually, unless an assignment specifies otherwise.

Some examples of what is not allowed by the conduct code: copying all or part of someone else's work, and submitting it as your own; giving another student in the class a copy of your assignment solution; consulting with another student during an exam. If you have questions about what is allowed, please discuss it with the instructor.

Violations of the Student Conduct Code will be filed with the Office of Student Conduct, and appropriate sanctions will be given.

 

Course Outline

  • Introduction
    • Basic Concepts
    • Example: Convex Hull in 2D
  • Line segments intersection
    • Plane Sweep algorithm
    • Planar graphs, Euler's Formula
  • Polygons and Triangulations
    • Art Gallery problem,
    • Geometric dual graphs
    • Polygon triangulation,
    • Monotone partitionning
  • Range Search
    • Range search and count
    • K-d trees
    • Quad trees
    • R, R+ trees
  • Proximity
    • Closest pair
    • All nearest neighbors (Voronoi Diagram)
    • Euclidean Minimum Spanning Tree
    • Euclidean Traveling Salesman Problem
  • Delaunay triangulation
    • Delaunay graph
    • Duality with Voronoi Diagram
    • Randomized incremental algorithm
    • Relation with convex hulls
  • Motion planning and Visibility Graphs
    • Minkowski sums
    • Mapping obstacles in configuration space
    • Point and polygon robot motion
    • Visibility graphs
    • Shortest route
  • Mesh Generation
    • unifrom and non-uniform meshes
    • meshes and quad trees
  • Point Location
    • Trapezoidal maps
    • Incremental randomization construction of trapezoidal maps
    • The Directed Acyclic Graph
  • Linear Programming
    • The geometry analogy
    • Randomized incremental algorithm
    • Examples