Organisers: Marc van Kreveld and Bettina Speckmann

Intended audience: PhD students in spatial sciences, GIScience professionals interested in algorithms.

Prerequisites: Attendees are assumed to have some elementary knowledge of math and programming. See the bottom of this page for details.

Topic: This tutorial gives an overview of the basics of algorithms and their efficiency analysis. We introduce some basic terminology (efficiency, complexity, asymptotic running time, intractability, NP-completeness) without going into mathe-matical detail. We explain why certain problems cannot be solved exactly at all, and how approximation algorithms work. We explain what combinatorial complexity of certain structures means, and how it can be useful. Then we pro-ceed with a number of computational problems arising in GIScience, and how algorithms and efficiency analysis can help with their (efficient) solution.

We believe that algorithms for GIScience should be developed through collaborations of experts from GIScience and Algorithms. Hence it is not necessary to teach GIScientists to perform the rather technical, mathematical analysis used in algorithm theory. Therefore we do not concentrate on techniques for the design of efficient algorithms, but on using geometric algorithms to solve important problems in GIScience. Furthermore, we attempt to create an under-standing of algorithmic concepts and ideas among (future) researchers in the spatial sciences, in order to allow for a better mutual understanding and collaboration.

The examples we use include basic geometric problems like computing the smallest distance or Hausdorff distance between two polygonal lines, or computing clusters, but also problems more closely related to GIScience like analysis of trajectories, and the computation of visualizations of spatial data.

Format: The tutorial will consist of a series of lectures with plenty of room for interaction and questions. Attendees are invited to ask questions at all times. The smaller the group, the more possibilities for interaction will arise. Lectures are chosen as format, because the main objective is creating awareness and providing basic information. We believe that lectures are most efficient for conveying information and starting interaction. They allow us to discuss the main points of algorithms and efficiency in a half-day tutorial.

As stated above, it is not our objective to train the attendees to design algorithms and perform efficiency analyses, for which other forms of tutorials would be more effective. The use of many examples will help to make the topic more concrete, and to link to computational problems the attendees may have encountered before.

In addition, we are available before or after the tutorial to meet with interested participants to give feedback and advice on algorithmic issues arising in their work.

Outline:

Basic concepts in algorithms and efficiency (30 min.)
Introduction of basic concepts in algorithms and efficiency through a set of basic questions: How is the big-O defined? How can efficiency be analyzed? What is worst-case efficiency analysis? How appropriate is worst-case efficiency analysis? What is the efficiency of basic algorithmic problems that one encounters in GIScience?
10 minute break
NP-completeness and approximation (30 min.)
Introduction of the concept of NP-completeness, its definition, and its influence on algorithm design. Furthermore, the topic of approximation algorithms is treated. Again a number of basic questions will be the guiding principle: How do you recognize that a problem may be NP-complete? What do you do if a problem is NP-complete? What is the difference between a heuristic and an approximation algorithm? In what situations do you use approximation algorithms? What are typical GIScience problems that are NP-complete?
15 minute break
Examples of algorithms and efficiency, I (40 min.)
Through a sequence of GIScience problems that involve computation, examples of algorithm design and efficiency analysis will be given. These GIScience problems include cartographic operations like annotating maps and producing cartograms, and spatial analysis operations like clustering, reconstruction from LiDAR data, and trajectory analysis.
15 minute break
Examples of algorithms and efficiency, II (40 min.)
More examples.

 

Organizers: Marc van Kreveld is professor at the Virtual Worlds division of the Department of Information and Computing Sciences at Utrecht University. Bettina Speckmann is professor at the Algorithms group of the Department of Mathematics and Computer Science at the Eindhoven University of Technology. Both organizers are well-established researchers in computational geometry and have been quite active in GIScience research as well. They have many years of experience in teaching bachelor and master courses, and regularly achieve very high scores by students on their teaching evaluations. They both hold teaching awards from their departments.

Detailed prerequisites

Familiar with functions like

  • quadratic functions
  • polynomials
  • square roots
  • logarithmic functions
  • exponential functions

and basic calculations involving these.

Familiar with basic geometry like

  • cartesian coordinates of points like p=(2,5)
  • equations like y=3x+4 to represent lines
  • computing the length of a line segment (Pythagoras' Theorem)

Basic facts

  • two distinct points define a line through them
  • three distinct and not collinear points define a circle through them

Familiar with basic programming (in Java, C++, ...)

  • assignments: x = x + 1
  • for-loops: for i=1 to 10 do
  • while-loops: while ((i<10) and (j>k)) do
  • calling other methods/subroutines/functions/procedures