Skip to main content Skip to navigation
Manoj Karkee Agricultural Automation and Robotics Lab

BSysE552 – Data Structures and Algorithms for Geographic Information Systems



Manoj Karkee (


Algorithmic Foundations of Geographic Information Systems, Marc van Kreveld, Juig Nievergelt et. el, editors.


  • GIS: A computing perspective. Worboys and Dukham. Second edition.
  • Computational geometry. M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkoph.


Week 1 and 2 (May 7 to May 20):

  • Spatial Data Structures
    • Vector and Raster Representation
    • Voronoi Diagrams and Delaunay Triangulations
    • DCEL Data Structure
    • Quad-edge data structure

Week 3  and 4 (May 21 to June 3):

  • Digital Elevation Models and TIN algorithms
    • Flow direction and Flow accumulation
  • Graphs and Search Algorithms; Dijkastra’s Algorithm

Week 5 and 6 (June 4 to June 17):

  • Geometric Algorithms
    • Divide and conquer, line sweep and incremental construction
    • Area of triangle, area of a convex and non-convex polygon
    • Orientation test, collinearity, betweenness, segment intersection test
    • Point-in-polygon, Convex hulls, Closest pair points

Week 7 and 8 (June 18 to July 1st):

  • Line and Terrain simplification Algorithms
  • Visibility; Visibility of Terrains

Week 8 and 9 (July 2nd to July 15th):

  • Visualization and Virtual Reality
    • Visualization of TIN
    • Hidden Surface Removal
    • Level of Details
    • Virtual reality hardware and software; Cluster Computing, CAVE

Week 10 (July 16th to July 22):

Final Project