COMP 163/MATH 181 Computational Geometry Fall 2022 
Announcements 
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, computeraided 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, farthestpairs and closestpairs, 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:0010:15AM [R+ block]: JCC 140 
Class # 1:
Wednesday, September 7: Introductions; Upper and Lower Bounds for Convex Hull
...
Class # 2: Monday, September 12: GiftWrapping, 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 14
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 DoublyConnectedEdgeLists (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 58
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 912
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 1416
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 1720
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 2125
Class #26: Monday, December 12: 2nd test. Augmentations due 36 hours later.
Project Presentations (in exam slot): Tuesday, December 20, 8:0011: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, 910: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, 4393. 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) 