CS97 — Senior Conference

Class info | Instructor info | Schedule | Grading | Academic Integrity | Links
Computational Geometry with Applications in Geographic Information Systems


Welcome to CS97: Senior Conference! This year's topic will be on computational geometry and algorithms for Geographic Information Systems (GIS). Computational geometry studies problems relating to geometric objects such as points, lines, and polygons. GIS looks at many of the same problems in a geographic context where points can represent fire hydrants, lines can represent roads, and polygons can represent county boundaries. We'll look at some classical computational geometry topics such as convex hulls, line segment intersection, planar point location, Voronoi diagrams, and Delaunay triangulations. Then we will look at some applications in GIS including vector map overlays, nearest neighbor queries, and perhaps surface modeling.

Goals for the course

By the end of the course, we hope that you will have developed the following skills:


Class info

Room: Science Center 252
Time: TR 9:55am-11:10am
Text: Computational Geometry: Algorithms and Applications by M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf (the "three Marks/Marcs" book)

Instructor info

Professor: Andrew Danner
Office: Science Center 253
Phone: (610) 328-8665
Office hours: by appointment


1 Jan 22   Intro hw1
Jan 24   Convex Hulls
2 Jan 29   hw2
Jan 31 Drop/Add ends (Feb 01) Line Intersection, Overlay
3 Feb 05   hw3
Feb 07   Orthogonal Range Searching
4 Feb 12   hw4
Feb 14   Planar Point Location
5 Feb 19   hw5
Feb 21  
6 Feb 26   Voronoi Diagrams hw6
Feb 28  
7 Mar 04   Delaunay Triangulations hw7
Mar 06  

Mar 11

Spring Break

Mar 13

8 Mar 18   TIN Algorithms hw8
Mar 20 Project Proposals No Reading
9 Mar 25   Skip Quadtrees hw9
Mar 27 Last day to declare CR/NC or
Withdraw with a "W" (Mar 28)
No Reading
10 Apr 01   Linear Clustering hw10
Apr 03 Progress Report Research for Final Project
11 Apr 08   hw11
Apr 10   Redistricting in GIS. Connected Components
12 Apr 15   Dynamic MST hw12
Apr 17 Review Draft LCA
13 Apr 22   Wrapup  
Apr 24 Review Feedback Final Project talks  
14 Apr 29 Presentations  
May 01  

May 17

Final Paper Due


Grades will be weighted as follows:
15% Paper summaries/class participation
15% Paper presentations
15% Mini-Projects/homework
5% Project proposal/Lit Review
10% Rough Draft
10% Reviewer Comments
10% Project Presentation
20% Final Paper

Academic integrity

Strong academic integrity is expected of every student. Plagiarism, cheating, and academic dishonesty will be reported to the College Judiciary Committee and dealt with severely. You may not hand in work done by someone else as your own. You may discuss ideas and problems with others on a general level and such discussions are encouraged, but you must credit any collaborators or resources used in the completion of your assignments and projects.

External links

Have any good links that are relevant to the course? Let me know, and I'll add them here.
Wikipedia entry for Computational Geometry
Symposium on Computational Geometry (SoCG, or "sausage") proceedings.
Geometry Algorithms
Voronoi animation (Thanks Kit)
MSR's Tiled Vectors