COT 4521: Computational Geometry (Fall 2020/2019/2018)

Instructor: Paul Rosen
Location: CPR 122
Time: T/H 9:30am-10:45am

Course Description

Computational Geometry is the study of efficient algorithms to solve geometric problems. Topics covered include polygonal triangulations, polygon partitioning, convex hulls, Voronoi diagrams, arrangements, search and intersection, motion planning, and data analysis. These methods enable you to design efficient solution of numerous geometric problems that arise in other application areas such as astronomy, geographic information systems, CAD/CAM, data mining, graph drawing, graphics, medical imaging, metrology, molecular modeling, robotics, signal processing, textile layout, typography, video games, and vision. 

Learning Outcomes

  • Students will understand the objectives of various geometric computing problems and algorithms.
  • Students will understand the implementations and tradeoffs between various methods for solving geometric problems.
  • Students will be able to apply geometric approaches to solving computing problems in computer graphics/games, data analysis, user interface design, etc.

Books

  • Required: Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars, Computational Geometry: Algorithms and Applications, 3rd Edition, Springer, ISBN 978-3540779735

Course Work

Lecture Slides

Schedule

  • Week 1/2: Introduction to Computation Geometry & Processing
  • Week 3/4: Line and Segments Intersections (Ch 2)
  • Week 5: Polygon Preliminaries (Ch 3)
  • Week 6: Polygon Intersection (Ch 3)
  • Week 7: Art Gallery Problem & Polygon Triangulation (Ch 3)
  • Week 8: Polygon Partitioning & Monotone Triangulation (Ch 3)
  • Week 9/10: Convex Hulls (Ch 11)
  • Week 11: Voronoi Diagrams (Ch 7)
  • Week 12: Delaney Triangulations (Ch 9)
  • Week 13: Search (Ch 5, 6, 12)
  • Week 14: Clustering
  • Week 15: Project Presentations, Flex/Recap/Review
  • Final Exam: Thursday, December 10, 7:30-9:30 am
All dates and course content are subject to change.