Instructor: Alex Steiger (asteiger AT cs.duke.edu)
Time: WF 10:05am-11:20am
Location: BioSci 063
Office Hours: Tues @ 2-3pm and Wed @ 3-4pm in D312 LSRC, and by appt. Please email if interested in attending OH via Zoom.
Course Description: Computational geometry is a fundamental area of study in computer science with a wide breadth of applications, such as robotics, graphics, vision, geographic information systems, and biology. This course is an accessible introduction to the field through a hands-on, project-based approach. We will explore the design, analysis, implementation, and application of algorithms for various geometric problems, with an emphasis on putting theory into practice through the programming projects. There are no exams.
Prerequisites: CompSci 201 or equivalent, specifically using basic data structures to design and implement algorithms via object-oriented programming and analyzing their asymptotic runtimes. There are no other prerequisites.
Topics (tentative, may change in response to collective interests):
- Similarity search queries for spatial datasets via kd-trees and range trees
- Windowing queries via interval and segment trees
- Geometric primitives (“building blocks” of geometric algorithms)
- Convex hulls
- Dynamic data structures for evolving datasets
- Point location via ray-shooting and persistent data structures
- Polygon triangulation and boolean operations
- Delaunay triangulations and applications, e.g., to terrain modeling
- Voronoi diagrams with applications to nearest-neighbor search and path planning
- Map overlays via segment intersection
- Painter’s algorithm via binary space partitions
- Mesh generation via quadtrees
- Low-dimensional linear programming
- Visibility graphs and combinatorial robot motion planning
- Heuristical robot motion planning
Learning Objectives:
- Implement and apply key geometric algorithms and data structures to solve practical computational problems.
- Analyze the performance of geometric algorithms, formally and empirically.
- Use existing software tools and libraries to effectively implement and visualize geometric computations.
Assessment: There will be seven programming projects, where six are worth 12% and one is worth 14%, for a total of 86%. The remaining 14% is awarded for engagement: 0.5% per lecture (four absences allowed) for participating in exercises/discussions and 2% for completing course surveys/evaluations.
Textbook: Computational Geometry: Algorithms and Applications by de Berg et al. The 2nd or 3rd editions suffice for our class. Any other resources will be provided on Canvas.
Programming Environment: This course assumes familiarity with object-oriented programming, satisfied by CompSci 201. Our projects are in Python 3.9+, but you do not need knowledge of Python in particular. You may use any editor, but we recommend Visual Studio Code, PyCharm, and Juypter. The following resources may be useful:
- Python Anaconda Distribution for Scientific Computing https://www.anaconda.com/download/success/
- Visual Studio Code tutorial for Python 3: https://code.visualstudio.com/docs/python/python-tutorial
- PyCharm Development Environment: https://www.jetbrains.com/pycharm/
- Python tutorial: https://docs.python.org/3/tutorial/
Image credits: anonymous (https://commons.wikimedia.org/wiki/File:Coloured_Voronoi_3D_slice.svg), “Coloured Voronoi 3D slice”, https://creativecommons.org/licenses/by-sa/3.0/legalcode, accessed 8/24/2024
