|
Advanced Computational Geometry (Fall 2008)
|
|
|
Objectives
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:
- design and analyze algorithms for geometrical problems
in kinetic, streaming and online settings.
Contents
This course covers advanced topics in computational geometry
(mentioned in the course plan below) along with selected applications.
Lecturers
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
| 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
Literature
- [SA] Micha Sharir and Pankaj K. Agarwal,
Davenport-Schinzel
Sequences and their Geometric Applications, Cambridge
University Press, 1995.
- [Basch] Julien Basch, Kinetic Data Structures, PhD
Thesis, Stanford University, 1999.
- [Abam] Mohammad Ali Abam, New Data
Structures and Algorithms for Mobile Data, PhD Thesis,
Eindhoven, 2007.
- [handbook] Handbook
of Discrete and Computational Geometry, Chapman & Hall/CRC, Second Edition, 2004.
- [Narasimhan] Giri Narasimhan,
Geometric Spanner Networks, Cambridge University Press, 2007.
- [Muthukrishnan] S. Muthukrishnan Data
Streams: Algorithms and Applications (Foundations and Trends in
Theoretical Computer Science), Now Publishers Inc., 2005.
- [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.
- [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.
Quarter
2nd (Fall 2008).
Credits
5 ETCS points.
Prerequisites
Course language
English.
Compulsory programme
Homework handin.
Evaluation
Based on mandatory hand-in's and attendance, pass/fail.