Swarthmore CS97 Senior Conference Fall 2006

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 algorithms in GIS including methods for processing elevation data sets. It is hoped that many of the student projects can use real-world geographic data and visualize the data and results in a real working GIS.

Announcements

This course has ended
The Final Presentation schedule is posted
Project ideas
Project instructions pdf
Latex style files
A simple GIS demo
Helpful GIS tools

Class info

Room: Science Center 252
Time: Wednesdays 1:15pm–4:00pm

Instructor info

Professor: Andrew Danner
Office: Science Center 253
Phone: (610) 328-8665
Office hours: Tu/Th 9:00am-12:00pm or by appointment

Schedule

Day	Notes	Topic	Presenter(s)	Snacks
Sep 6		Introduction to Comp. Geom. and GIS	Andy	Andy
Sep 13		Convex Hulls Handout from O'Rourke Computational Geometry in C W. Eddy A New Convex Hull Algorithm for Planar Sets	Phil, Shingo, and Alex	Anthony
Sep 20		G. Toussaint Solving Geometric Problems with the Rotating Calipers J. Hershberger and J. Snoeyink Speeding Up the Douglas-Peucker Line-Simplification Algorithm	Mustafa, and Scott	Mustafa
Sep 27		D. Izraelevitz A Fast Algorithm for Approximate Viewshed Computation J. Bentley and J. Friedman Data Structures for Range Searching Agarwal et al. From Point Cloud to Grid DEM: A Scalable Approach [OPTIONAL] W. R. Franklin and C. K. Ray Higher isn't Necessarily Better: Visibility Algorithms and Experiments [OPTIONAL] B. Kaucic and B. Zalik Comparison of Viewshed Algorithms on Regular Spaced Points [OPTIONAL] Digital Panoramas of various mountain ranges	Matt, Giovanna, and Anthony	Scott
Oct 4		S. K. Jenson and J. O. Domingue Extracting Topographic Structure form Digital Elevation Data for GIS Analysis L. Toma et al. Flow Computation on Massive Grids J. Garbrecht and L. Martz The assignment of drainage direction over flat surfaces in raster DEMs P. Soille et al. Carving and adaptive drainage enforcement of grid digital elevation models	Steve, Bronwyn, and Dan	Phil
Oct 11		Handout on Point Location N. Sarnak and R. Tarjan Planar Point Location Using Persistent Search Trees Handout on Line Segment Intersection	Giovanna, Phil, and Alex	Steve
Oct 18	No Class — Fall Break
Oct 25		Handout on Voronoi Diagrams M. Ramella et al. Finding galaxy clusters using Voronoi tessellations Steve's handy astro guide doc [OPTIONAL] F. Aurenhammer Voronoi Diagrams — A Survey...	Shingo (5.1-5.3), Bronwyn (5.4-5.5), Scott (5.6-END), and Steve (A&A)	Alex
Nov 1	Project Teams/Ideas Due	A Fabri et al. On the design of CGAL a computational geometry algorithms library M. van Kreveld Digital Elevation Models and TIN Algorithms (Sections 1.1–1.4 only)	Taylor, Mustafa	Bronwyn
Nov 8	Expanded Proposal Due	Demo of GRASS GIS by Andy M. van Kreveld Digital Elevation Models and TIN Algorithms (Sections 1.5–end)	Phil	Giovanna
Nov 15	GIS Competency Day	P. Lindstrom and V. Pascucci Visualization of Large Terrains Made Easy [OPTIONAL] P. Lindstrom and V. Pascucci Terrain Simplification: A General Framework for View-Dependent Out-of-Core Visualization C. J. Koucmoud and D. H. House A Constraint-Based Approach to Constructing Continuous Cartograms D. A. Keim, C. Panse, and S. C. North Medial-Axis-Based Cartograms	Matt, Bronwyn, and Anthony	Shingo
Nov 20	Monday	M. McAllister and J. Snoeyink Extracting Consistent Watersheds from Digital River and Elevation Data K. L. Verdin and J. P. Verdin A Topological System for Delineation and Codification of the Earth's River Basins	Shingo and Dan	Andy
Nov 29		Project Summaries		Matt
Dec 6		Point/Line Duality and Applications		Dan
Dec 13		Final Presentations		Taylor

Grading

Grades will be weighted as follows:
20% Paper summaries/class participation
20% Paper presentations
5% Project proposal
5% Literature 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
USGS seamless elevation data
NC Floodmaps
TIGER/Line US Census data
Philadelphia GIS data
ESRI Map Museum

CS97 — Senior Conference