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.
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 |