1. Introduction to Geographic Information Systems, Spatial Information, and Geometric Algorithms
Basic principles of spatial information and geographic information systems. Examples of GIS applications. Introduction to geometric algorithms. Relationship between GIS implementation and geometric algorithms.
2. Map Representation, Combination, and Overlay of Geographic Subdivisions
Introduction to map overlay. Data structures for representing maps and geographic subdivisions. Algorithms for computing overlays of subdivisions. Algorithms and data structures for locating points in geographic subdivisions.
3. Digital Terrain Models, Vector and Raster Terrains
Models for representing terrains. Raster models and TINs (Triangulated Irregular Networks). Basic algorithms for rasters and TINs. Traversal and localization in TINs. Conversion between different terrain models.
4. Algorithms for Terrain Analysis: Visibility and Hydrology Problems
Applications of terrain analysis in visibility and hydrology. Calculating viewsheds and watersheds in rasters and TINs. Removal of local minima and other artifacts.
5. Voronoi Diagrams Applied to Facility Location Problems and Geographic Pattern Analysis
Definition of the Voronoi diagram. Applications to GIS. Algorithms for constructing the Voronoi diagram. Spatial analysis: position-based and distance-based. Cluster detection. Spatial interpolation.
6. Basic Algorithms for Digital Cartography: Map Generalization and Map Labeling
Introduction to maps and cartography. Principles of map design. Cartographic symbolization and generalization. Line simplification, Douglas-Peucker algorithm. Map labeling.
7. Extension to Specific Topics Chosen by Students
Specific topics will be defined by students and instructors during the first half of the course.