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.
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 five programming projects, where four are worth 16% and one is worth 22%, 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
