Swarthmore CS97 Senior Conference Spring 2008

Introduction

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:

Analyze and critically discuss research papers in writing and in class
Formulate and evaluate a hypothesis by proposing, implementing and testing a project
Relate project to prior research via a review of related literature
Write a coherent, complete paper describing and evaluating a project
Orally present a clear and accessible summary of a research work
Understand the fundamental questions in computational geometry and analyze different solutions to these questions

Announcements

Final Presentation schedule is posted.
Final project guidelines pdf
Final Projects from 2006 are available for perusal
Old project ideas from 2006. Some might be good projects this year too.
Latex style files

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

Schedule

WEEK	DAY	ANNOUNCEMENTS	TOPIC & READING	HOMEWORK
1	Jan 22		Intro	hw1
	Jan 24		Convex Hulls
2	Jan 29			hw2 Project1
	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

Grading

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
Flatland
Voronoi animation (Thanks Kit)
MSR's Tiled Vectors

CS97 — Senior Conference