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 ps |
Phil, Shingo, and Alex |
Anthony | |
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 |
Mustafa, and Scott |
Mustafa | |
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 |
Matt, Giovanna, and Anthony |
Scott | |
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 |
Steve, Bronwyn, and Dan |
Phil | |
Oct 11 | Handout on Point Location N. Sarnak and R. Tarjan Planar Point Location Using Persistent Search Trees ps 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 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) |
Alex | |
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) |
Taylor, Mustafa |
Bronwyn |
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 |
Shingo |
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 Dan |
Andy |
Nov 29 | Project Summaries | Matt | ||
Dec 6 | Point/Line Duality and Applications | Dan | ||
Dec 13 | Final Presentations | Taylor |