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 ps
and Alex
Sep 20 G. Toussaint Solving Geometric Problems with the Rotating Calipers ps
J. Hershberger and J. Snoeyink Speeding Up the Douglas-Peucker Line-Simplification Algorithm ps
and Scott
Sep 27 D. Izraelevitz A Fast Algorithm for Approximate Viewshed Computation ps
J. Bentley and J. Friedman Data Structures for Range Searching ps
Agarwal et al. From Point Cloud to Grid DEM: A Scalable Approach ps
[OPTIONAL] W. R. Franklin and C. K. Ray Higher isn't Necessarily Better: Visibility Algorithms and Experiments ps
[OPTIONAL] B. Kaucic and B. Zalik Comparison of Viewshed Algorithms on Regular Spaced Points ps
[OPTIONAL] Mt. Diablo Viewshed Controversy (HTML)
[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 ps
L. Toma et al. Flow Computation on Massive Grids ps
J. Garbrecht and L. Martz The assignment of drainage direction over flat surfaces in raster DEMs ps
P. Soille et al. Carving and adaptive drainage enforcement of grid digital elevation models ps
and Dan
Oct 11 Handout on Point Location
N. Sarnak and R. Tarjan Planar Point Location Using Persistent Search Trees ps
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 pdf
Steve's handy astro guide doc
[OPTIONAL] F. Aurenhammer Voronoi Diagrams — A Survey... pdf
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 pdf
M. van Kreveld Digital Elevation Models and TIN Algorithms pdf (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 pdf (Sections 1.5–end)
Phil Giovanna
Nov 15 GIS Competency Day P. Lindstrom and V. Pascucci Visualization of Large Terrains Made Easy pdf
[OPTIONAL] P. Lindstrom and V. Pascucci Terrain Simplification: A General Framework for View-Dependent Out-of-Core Visualization pdf
C. J. Koucmoud and D. H. House A Constraint-Based Approach to Constructing Continuous Cartograms pdf
D. A. Keim, C. Panse, and S. C. North Medial-Axis-Based Cartograms pdf
Matt, Bronwyn,
and Anthony
Nov 20 Monday M. McAllister and J. Snoeyink Extracting Consistent Watersheds from Digital River and Elevation Data pdf
K. L. Verdin and J. P. Verdin A Topological System for Delineation and Codification of the Earth's River Basins pdf
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