Welcome to Geometric Spanners course homepage

The course deals with advance algorithms related to graphs, namely geometric spanners. The geometric spanner problem is closely related to several fundamental problems in geometric and graph algorithms, including the minimum spanning tree problem, the Steiner minimum tree problem, the shortest path problem, and more.

I assume that the attending have had previous exposure to basic concepts of algorithm design and analysis, data structures, probability and combinatorics, and mathematical proof techniques.

In this course, we will consider the following problem: Given a set P of n points in R^d, how to construct a "good" network that connects these points?

What do we mean by this? A network on a point set V is a connected graph G(V,E). When designing a network, several criteria are taken into account. For example, in many applications, it is important to ensure a short connection between every pair of points. For this it would be ideal to have a direct connection between every pair of points—the network would then be a complete graph—but in most applications, this is unacceptable due to the very high costs associated with constructing such a network. This leads to the concept of a spanners.

The goal in this course is to learn different algorithms to construct "good" network (spanners) having only few edges, the measure how good the network is, will also be discuss in the course.

Text Book

Giri Narasimhan and Michiel Smid. Geometric Spanner Networks

Grade Calculation

The course grade will be composed of 80% final exam, and 20% homework assignments.

Instructor:

Paz Carmi http://www.cs.bgu.ac.il/~carmip