|
COMP 163/MATH 181 Computational Geometry Fall 2022 |
|
|
Announcements |
- During the semester, announcements will be listed here (or possibly in Canvas or in Piazza), with
dates.
- Homework will be submitted over Gradescope. Here are draft guidelines for submitting homework solutions: pdf
- LATEX template, tex format, ps and pdf. See also LATEX resources.
|
Brief Description |
Computational geometry is concerned with the design and analysis of algorithms for solving geometric problems. Applications can be found in such fields as VLSI design, computer graphics, robotics, computer-aided design, pattern recognition, and statistics. The aim of the course will be to introduce some basic problems of computational geometry and discuss algorithms for solving these problems. The ultimate aim will be to identify general paradigms and data structures of particular importance to solving computational geometry problems, and thereby provide the participants with a solid foundation in the field.
Topics Covered: Design and analysis of algorithms for geometric problems. Topics include proof of lower bounds, convex hulls, searching and point location, plane sweep and arrangements of lines, Voronoi diagrams, intersection problems, decomposition and partitioning, farthest-pairs and closest-pairs, rectilinear computational geometry.
Expected Work:
Six written homework assignments, occasional spontaneous quizzes, two tests, an implementation/theory project, and scribing for 2 classes.
[When ready to submit notes, Login to the Tufts CS machines and type "provide cs163 classnotes file1 file2 ..." at the prompt. ]
PREREQUISITE: Computer Science 160 or a 100+ level Mathematics Course or Graduate Standing.
|
Schedule: MW, 9:00-10:15AM [R+ block]: JCC 140 |
Class # 1:
Wednesday, September 7: Introductions; Upper and Lower Bounds for Convex Hull
...
Class # 2: Monday, September 12: Gift-Wrapping, Graham's Scan, Incremental, Divide & Conquer .
Class # 3: Wednesday, September 14: Recap of Convex Hull Algorithms. Discussion of Data Structures. Quick Hull. Group Problem Solving.
Class # 4: Monday, September 19: Introduce Dynamic Convex Hulls (and "Order Decomposable Problems"). "Ultimate" algorithm for Convex Hull (and "Prune and Search" paradigm) .
Class # 5: Wednesday, September 21: Complete the discussion and proof of the $O(\log ^2 n)$ updates in the dynamic convex hull algorithm. Continued the discussion of Order Decomposable Problems.
Friday, September 23: First homework due at 11:59pm covering classes 1-4
Class # 6: Monday, September 26: Point inclusion with convex, monotone, and simple polygons. Computing the intersection points of an arrangement of lines in sorted order using line sweep.
Class # 7: Wednesday, September 28: Sweepline algorithm for line segment intersection. Regularizing planar subdivisions.
Class # 8: Monday, October 3: Reviewed regularizing planar subdivisions. Introduce Doubly-Connected-Edge-Lists (DCEL) as well as Quad Edge Data Structures. Detecting and Computing Intersections of Convex Polygons.
Class # 9: Wednesday, October 5: Planar Point Location
Friday, October 7: Second homework due at 11:59pm covering classes 5-8
Monday, October 10: UNIVERSITY HOLIDAY
Class #10: Wednesday, October 12: Duality and Least Median of Squares Regression using Vertical Line Sweep
Class #11: Monday, October 17: Recap and continuation of LMS Regression with Vertical Line Sweep and Introduction to Topological Line Sweep
Class #12: Wednesday, October 19: Topological Line Sweep
Friday, October 21: Third homework due at 11:59pm covering classes 9-12
Class #13: Monday, October 24: 1st test. Augmentations due 36 hours later.
...
Class #14: Wednesday, October 26: Voronoi Diagrams and Continuation of Topological Sweep
Class #15: Monday, October 31: Voronoi Diagrams
Class #16: Wednesday, November 2:
Friday, November 4: Fourth homework due at 11:59pm covering classes 14-16
Class #17: Monday, November 7:
Class #18: Wednesday, November 9:
Class #19: Monday, November 14:
Class #20: Wednesday, November 16: Convex Hulls in Higher Dimensions
Friday, November 18: Fifth Homework Due at 11:59pm covering classes 17-20
Class #21: Monday, November 21: Linear Programming
Class #22: Monday, November 28: Geometric Data Structures
Class #23: Wednesday, November 30: Rectilinear Computational Geometry
Class #24: Monday, December 5: TBA
Class #25: Wednesday, December 7:
Friday, December 9: Sixth Homework Due at 11:59pm covering classes 21-25
Class #26: Monday, December 12: 2nd test. Augmentations due 36 hours later.
Project Presentations (in exam slot): Tuesday, December 20, 8:00-11:00AM
Project materials due by noon on Monday, December 20.
Login to the Tufts CS machines and type "provide cs163 project file1 file2 ..." at the prompt.
-->
|
Homework |
This list will be created during the
semester. I expect there to be six (6) homeworks, with one due roughly every two weeks, and a final project.
Instructor:Diane L. Souvaine |
Teaching Assistants:Jake (dot) Sturim (at) tufts (dot) edu Office Hours: Fridays, 9-10:30AM
|
|
TextBooks and References |
|
|
Main textbook |
|
|
Joseph
O'Rourke |
|
|
Satyan L. Devadoss and Joseph
O'Rourke |
|
|
Joseph
O'Rourke and Csaba Tóth |
|
|
Franco P. Preparata,
Michael Ian Shamos |
|
|
D. P. Dobkin and D. L. Souvaine, Computational Geometry -- A User's Guide. Chapter 2 of Advances in Robotics 1: Algorithmic and Geometric Aspects of Robotics, J. T. Schwartz and C. K. Yap, eds., Lawrence Erlbaum Associates, 1987, 43-93. User Guide |
|
|
D. L. Souvaine Lecture Notes in Computational Geometry, 2005: Lecture Notes. |
|
|
|
|
Resources |
|
|
|
|
|
Demos |
|
|
|
List of Computational Geometry Demos maintained by Jeff Erickson, |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Documentation of LEDA book (Thanks to Cory McMahon) |
|
Other computational Geometry |
|
|
|
|
|
|
|
|
Document Preparation with Latex, by Budgen and Nelson. (Excellent) Getting Started with Latex, by Wilkins. (Shorter but good for getting started) |