CS97 — Senior Conference

Class info | Instructor info | Schedule | Grading | Academic Integrity | Links
Computational Geometry and Algorithms for 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 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.


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


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
and Alex
Sep 20 G. Toussaint Solving Geometric Problems with the Rotating Calipers
J. Hershberger and J. Snoeyink Speeding Up the Douglas-Peucker Line-Simplification Algorithm
and Scott
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
and Anthony
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
and Dan
Oct 11 Handout on Point Location
N. Sarnak and R. Tarjan Planar Point Location Using Persistent Search Trees
Handout on Line Segment Intersection
and Alex
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)
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)
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
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
Nov 29 Project Summaries Matt
Dec 6 Point/Line Duality and Applications Dan
Dec 13 Final Presentations Taylor


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