Advanced Computational Geometry (Fall 2008)


The participants after the course will know how to deal with some fundamental problems of computational geometry in kinetic, streaming and online settings. They will also have knowledge of some advanced techniques in computational geometry.

Learning outcomes and competences

The participants must at the end of the course be able to:


This course covers advanced topics in computational geometry (mentioned in the course plan below) along with selected applications.


Mohammad Ali Abam, S. Srinivasa Rao, and Deepak Ajwani.

Time and Place

Tuesday 10.15-12.00 and Thursday 11.15-12.00, Turing 014

Course plan

Week Date Content Literature
45 4/11 Davenport-Schinzel sequences  [SA] 
45 6/11 Davenport-Schinzel sequences  
46 11/11 Conflict-free coloring  [HS05], [Chen et al.] 
46 13/11 Conflict-free coloring   
47 18/11 Kinetic data structures  [Basch], [Abam]
47 20/11 Kinetic data structures   
48 25/11 Geometric spanner networks  [Narasimhan] 
50 11/12 Parametric search  Chapter 43 of [handbook] 
51 16/12 Parametric search   
3 16/1 Streaming  [Muthukrishnan], Chapter 6 of [Abam] 
4 22/1 Streaming   

Handin exercises


  1. [SA] Micha Sharir and Pankaj K. Agarwal, Davenport-Schinzel Sequences and their Geometric Applications, Cambridge University Press, 1995.
  2. [Basch] Julien Basch, Kinetic Data Structures, PhD Thesis, Stanford University, 1999.
  3. [Abam] Mohammad Ali Abam, New Data Structures and Algorithms for Mobile Data, PhD Thesis, Eindhoven, 2007.
  4. [handbook] Handbook of Discrete and Computational Geometry, Chapman & Hall/CRC, Second Edition, 2004.
  5. [Narasimhan] Giri Narasimhan, Geometric Spanner Networks, Cambridge University Press, 2007.
  6. [Muthukrishnan] S. Muthukrishnan Data Streams: Algorithms and Applications (Foundations and Trends in Theoretical Computer Science), Now Publishers Inc., 2005.
  7. [HS05] Sariel Har-peled, Shakhar Smorodinsky, On conflict-free coloring of points and simple regions in the plane, Discrete and Computational Geometry, Volume 34, Number 1, pp 47-70, 2005.
  8. [Chen et al.] Ke Chen, Amos Fiat, Haim Kaplan, Meital Levy, Jirí Matousek, Elchanan Mossel, János Pach, Micha Sharir, Shakhar Smorodinsky, Uli Wagner, and Emo Welzl, Online Conflict-Free Coloring for Intervals, SIAM Journal on Computing, Volume 36, Issue 5, pp. 1342-1359, 2006.


2nd (Fall 2008).


5 ETCS points.


Course language


Compulsory programme

Homework handin.


Based on mandatory hand-in's and attendance, pass/fail.

This page is maintained by S. Srinivasa Rao <>