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
- Worksheet 1 – Geometry and Algorithms Review
- Worksheet 2 – Segment/Segment AABB Intersection
- Worksheet 3 – Segment/Segment Sweep Intersection
- Worksheet 4 – Polygon Basics
- Worksheet 5 – Polygon Intersection
- Worksheet 6 – Art Gallery Problem
- Worksheet 7 – Polygon Triangulation
- Worksheet 8 – Monotone Partitioning and Triangulation
- Worksheet 9 – Convex Hulls (QuickHull & Graham’s)
- Worksheet 10 – Convex Hulls (Incremental & Divide-and-Conquer)
- Worksheet 11 – Voronoi Diagram (Insertion)
- Worksheet 12 – Voronoi Diagram (Divide-and-Conquer)
- Worksheet 13 – Delaunay Triangulation
- Worksheet 14 – Spatial Organizations and Query
- Worksheet 15 – Clustering
- Project 0 – Introduction to Processing (skeleton code)
- Project 1 – Line Segment Intersections (skeleton code)
- Project 2 – Polygon Diagonals (skeleton code)
- Project 3 – Gift Wrapping Convex Hulls (skeleton code)
- Final Project
Lecture Slides
- Module 1 – Introduction
- Module 2 – Preliminaries
- Module 3 – Introduction to Processing
- Module 4 – Segment Intersection
- Module 5 – Segment Intersection (AABB)
- Module 6 – Segment Intersection (Sweep)
- Module 7 – Polygons
- Module 8 – Convex Polygon Intersection
- Module 9 – The Art Gallery Problem
- Module 10 – Polygon Triangulation
- Module 11 – Polygon Partitioning
- Module 12 – Monotone Triangulation
- Module 13 – Convex Hulls
- Module 14 – Voronoi Diagram
- Module 15 – Voronoi Diagram (Fortune)
- Module 16 – Delaunay Triangulation
- Module 17 – Point Searches
- Module 18 – Clustering
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