Here is a couple of Geometric Algorithms used in GIS.

  • Convex hull problem: for a set of points, determine the smallest convex set that contains all.
  • Line segment intersection: for a set of line segments, determine all intersections.
  • Voronoi diagram computation: for a set of points, determine the subdivision of the plane into cells such that inside some cell, one and the same point of the set is closest.
  • Delaunay triangulation: for a set of points, determine a planar subdivision by creating edges between the input points in such a way that no two edges intersect, all faces are triangles, no more edges can be added with the given constraints, and no circumcircle of any triangle contains an input point in its interior.
  • Minkowski sum: for two simple polygons P and Q, compute the shape that consist exactly of the sum of all points of P and all points of Q, where sum is interpreted as the vector sum.
  • Rectangular range search: for a set of points in the plane, design a data structure on those points, such that for every axis-parallel query rectangle, all points in the data structure that lie in the query rectangle can be reported efficiently. Algorithms are needed for the construction of the data structure and for the execution of a query.

2007-11-16_062422.png

Reference:
M Kreveld, Computational Geometry: Its objectives and relation to GIS, Institute of Information and Computing Sciences, Utrecht University